TL; DR: As Chuck already mentioned, Ruby doesn't have TCO. However doing one recursion and not two has big impact on how much stack you use and how many iterations are done. With this answer I just want to point out that at some time the memoization version is better than the iterative version. NB: I'm not a ruby programmer. It may not be idiomatic code.
The test shows the iterative approach is so fast it can generate fib of 1..50 from scratch just as fast as your memoization version reuses computation in each of the method calls above 3.
I think 1..50 is done so fast that it's not a very reliable to see if iteration actually is faster. I changed the memopization version to:
# Initialize the memoization array.
@scratchpad = []
# Calculate the nth Fibonacci number, f(n).
def fibo (n)
if n <= 1
return n
end
if @scratchpad[n].nil?
@scratchpad[n] = fibo(n-1) + fibo(n-2)
end
return @scratchpad[n]
end
I then changed the loop to this:
(1..5000).each { |number|
fibo(number) # no need to time character output
}
Here are the results on my computer:
Iteration: 6.260000 0.010000 6.270000 ( 6.273362)
Memoization: 0.000000 0.000000 0.000000 ( 0.006943)
I used:
ruby -v
ruby 1.9.3p194 (2012-04-20 revision 35410) [x86_64-linux]
Increasing the memoization version to 1..50000 still returned a lot faster than the iteration version. The reason is that the iteration starts from scratch each time while the memoization version has a more ineffective algo but the memoization makes it only recurse max two times for each number since we have fib(n-1)
and fib(n-2) in the array when calculating
fib(n)`.
The slowest has O(fib(n))
of course. The iterative has O(n)
. With memoization the fib(n-2)
is free when calculated fib(n-1)
so we are back to O(n)
but in your test you calculate the previous fibonacci number before the next so in practice each individual iteration from 1..x
is O(1)
. If you were to start with the highest number the first iteration would be O(n)
and every next would be O(1)
.