From: Marcin Raczkowski <mailing.mr@...>
Date: 2007-09-18T23:37:52+09:00
Subject: Re: Faster Alternatives for Recursion in Ruby -Assignment

Ruby Newbie wrote:
> I have the following assignment to be done.I have written the recursive
> API and a loop based solution but what is the faster alternative for
> these two that can figure into that "fastfunk(n)" method. Thanks for
> your help in advance.
> 
> Funkonacci Numbers:
> Define the Funkonacci numbers as follows:
>   0  if n < 1
>         funk(n) =  1  if n = 1
>   funk(n - 1) - (2 × funk(n - 2))  otherwise
> 
> Write a method funk(n) that calculates the nth Funkonacci number
> recursively. Generate a few Funkonacci numbers.  Now write a second
> method, fastfunk(n) that calculates the nth Funkonacci number more
> quickly
> 
> def funkn(n)
>   return 0 if n<=0
>   return 1 if n==1
>   funkn(n - 1) - (2 * funkn(n - 2))
> end
> def funknloop(n)
>   return 0 if n<=0
>   return 1 if n==1
>   i1 , i2  = 0,1
>   for i in 2...(n+1)
>   num = i2 - 2*i1
>   i1 ,i2 = i2, num
> end
> i2
> end
> 
> puts funkn(10)
> puts funknloop(10)

I think there was nice acronym for "do your homework yourself" or 
something similar

but since I'm doing everything except learn for my final so here it's

to calculate N th fibonacci number

def rfib(n)
   return 1 if n<3
   rfib(n-1) + rfib(n-2)
end

def ifib(n)
   return 1 if n<3
   a,b = 1,1
   (n-2).times do
     a,b = b, a+b
   end
   b
end

to print all of them along the way: (and here's why iteration one is 
much faster - there's no easy way to print them without recalculating 
each time)

def rfib(n)
   return 1 if n<3
   rfib(n-1) + rfib(n-2)
end

10.times do |x|
   puts rfib(x+1)
end

def ifib(n)
   if n<2
     puts "1"
   elsif
     puts "1\n1"
   end

   a,b = 1,1
   (n-2).times do
     a,b = b, a+b
     puts b
   end
   b
end


no coments so you have more fun explaining how you did it on your CE 
class :)