From: Alphonse 23 <lists@...>
Date: 2013-06-06T18:31:44+09:00
Subject: Re: Need help understanding recursion.

Sorry, I realized that I should probably help you understand your
example as well.

----------------------

M = 'land'
o = 'water'

# So world is a 2d array, where M equals land and o equals water. The x
axis goes from left to right, and the y axis going from top to bottom.
world = [
  [o,o,o,o,o,M,o,o,o,o,o],
  [o,o,o,o,M,M,o,o,o,o,o],
  [o,o,o,o,o,M,o,o,M,M,o],
  [o,o,o,M,o,M,o,o,o,M,o],
  [o,o,o,o,o,M,M,o,o,o,o],
  [o,o,o,o,M,M,M,M,o,o,o],
  [M,M,M,M,M,M,M,M,M,M,M],
  [o,o,o,M,M,o,M,M,M,o,o],
  [o,o,o,o,o,o,M,M,o,o,o],
  [o,M,o,o,o,M,M,o,o,o,o],
  [o,o,o,o,o,M,o,o,o,o,o]]

# continent_size takes in the 2d array, and a beginning coordinate on
the map (x, y).
def continent_size world, x ,y

  # if current x or y is greater than 10 (10 would be beyond the bounds
of the array map) or less than 0 (there are no negative coordinates in
this example), then it returns 0.
  if x < 0 or x > 10 or y < 0 or y > 10
    return 0 # This condition(base-case) represents the bounds of the
map.
  end

  # if current coordinate is not equal to land than it returns 0.
  if world[y][x] != 'land'
    return 0
  end

  size = 1 # each coordinate equals 1 unit of measure.
  world [y][x] = 'counted land' # after a coordinate is visited it is
marked with 'counted land' so the method doesn't read the same
coordinate twice.

  # after marking the current coordinate with 'counted land' the method
calls itself on all adjacent coordinates. Adding 1 to size, marking a
coordinate that is land with 'counted land' if land is found, or adding
0 if 'water'/o is discovered. If 'counted land', 'water', or the bounds
of the map are discovered this is where the method terminates. If 'land'
is discovered, then it continues on to the other adjacent coordinates.
  size = size + continent_size(world, x-1, y-1)
  size = size + continent_size(world, x , y-1)
  size = size + continent_size(world, x+1, y-1)
  size = size + continent_size(world, x-1, y )
  size = size + continent_size(world, x+1, y )
  size = size + continent_size(world, x-1, y+1)
  size = size + continent_size(world, x , y+1)
  size = size + continent_size(world, x+1, y+1)
  size # this is what is returned.

end

puts continent_size(world, 5, 5)
# So what you get is the size of a land mass on the 10x10 map. Try
putting continent_size(world, 9, 2). It return 3 for the little island
in the top right. If you set the coordinates to a water coordinate, it
always returns 0.

This really isn't the best example to illustrate the concept of
recursion. It is simple though. Look up the towers of hanoi, that's a
much better (aswell as more common) elementary exercise to teach the
concept.

Hope this helped again.

pedro oliva wrote in post #1111496:
> Ive been reading Chris Pine's book 'Learn to Program' and its been going
> great up until I got to chapter 10 on recursion and thus has completely
> taken all my excitement from going forward. I understand that recursion
> is a method that will continue to call itself till there is an attribute
> to cause it to exit the loop. The example in the book though has me all
> sorts of confused. Can someone walk me through the example and bring
> back the excitement to continue to learn Ruby!

-- 
Posted via http://www.ruby-forum.com/.