Trying to understand the following code which returns the F(n) for the sequence number in the method call. It is actually from an older SO post. I do understand the Fibonacci numbers.
fib = Hash.new{ |h,k| h[k] = k < 2 ? k : h[k-1] + h[k-2]}
fib[6] # => 8
I know it's a Hash, and understand all the syntax. My stumbling block is the operation at the end of the line - h[k-1] + h[k-2]
Perhaps I do not fully understand the recursion method. Thanks for the help! .
That code is the same as the following:
fib = Hash.new do |h,k|
if k < 2
h[k] = k
else
h[k] = h[k-1] + h[k-2]
end
end
When you access a key that is not part of the hash fib it will default to whatever is in the block, where h is the hash itself and k is the key you want to access.
Using fib[6] the evaluation of if k < 2 returns false, so the else clause is executed:
h[k] = h[k-1] + h[k-2]
h[6] = h[6-1] + h[6-2]
h[6] = h[5] + h[4]
As you can see both h[5] and h[4] also try to access a non-existing key, so the same evaluation is made for both, and both return false from the condition in if, so:
h[5] = h[5-1] + h[5-2]
h[5] = h[4] + h[3]
h[4] = h[4-1] + h[4-2]
h[4] = h[3] + h[2]
Again, both h[3] and h[2] look for a non-existing key, so the process repeats:
h[3] = h[3-1] + h[3-2]
h[3] = h[2] + h[1]
h[2] = h[2-1] + h[2-2]
h[2] = h[1] + h[0]
Finally, the same goes with h[1] and h[0], but this time the condition in if will evaluate to true, so now it will return h[k] = k:
h[0] = 0
h[1] = 1
Now, after going all the way down, we go back up:
h[2] = h[1] + h[0]
h[2] = 1 + 0
h[2] = 1
h[3] = h[2] + h[1]
h[3] = 1 + 1
h[3] = 2
h[4] = h[3] + h[2]
h[4] = 2 + 1
h[4] = 3
h[5] = h[4] + h[3]
h[5] = 3 + 2
h[5] = 5
h[6] = h[5] + h[4]
h[6] = 5 + 3
h[6] = 8
So:
fib[6]
#=> 8
