Re: Need help understanding recursion.

pedro oliva <[e-mail]> wrote:
> 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!
> 
> 
> 
> M = 'land'
> o = 'water'
> 
> 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]]
> 
> def continent_size world, x ,y
> 
>   if x < 0 or x > 10 or y < 0 or y > 10
>     return 0
>   end
> 
>   if world[y][x] != 'land'
>     return 0
>   end
> 
>   size = 1
>   world [y][x] = 'counted land'
> 
>   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
> 
> end
> 
> puts continent_size(world, 5, 5)

What I would suggest is installing pry and using it to step through your
program.

If it's basic understanding of recursion that's lacking right now,
perhaps a simpler example might do as well. The most common introduction
to a recursive function is the factorial function, which is nominally
defined as:

   n is a postive integer
   n! == n * (n-1) ... * 1

so:

def factorial(n)
  raise "#{n} is not a postive integer!" unless (n.is_a?(Integer) && n > 0)
  return 1 if n == 1 # this is the stopping condition
  n * factorial(n-1) # this calculates the factorial
end
   
2.0.0p195 :006 > factorial(1)
 => 1 
2.0.0p195 :007 > factorial(2)
 => 2 
2.0.0p195 :008 > factorial(10)
 => 3628800 
2.0.0p195 :009 > factorial(0)
RuntimeError: 0 is not a positive Integer
2.0.0p195 :010 > factorial(-10)
RuntimeError: -10 is not a positive Integer
2.0.0p195 :011 > factorial('a')
RuntimeError: a is not a positive Integer
2.0.0p195 :012 > factorial(nil)
RuntimeError:  is not a positive Integer

2.0.0p195 :014 > (1..10).inject([]){|memo, obj| memo << factorial(obj)}
 => [1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800] 


Another beginner recursive example is the Fibonacci sequence (0, 1, 1,
2, 3, 5, ..)

def fibonacci(n)
  raise "#{n} is not a non-negative Integer" unless (n.is_a?(Integer) && n >= 0)
  return 0 if n == 0
  return 1 if n == 1
  fibonacci(n-1)+fibonacci(n-2)
end

2.0.0p195 :037 > (0..10).reduce([]){|m,o| m << fibonacci(o)}
 => [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55] 

I've tossed these up on https://gist.github.com/tamouse/5718918


Stick with Ruby! It's great!