Return values not working as expected in Ruby in a program that solves fibonacci sequence using dynamic programming

I'm new to ruby so I'm probably making a very newbie mistake here but I tried Googling for an answer and couldn't figure out the reason why this code is giving weird behavior. This code is very simple, and uses basic dynamic programming to store intermediate result to a Hash so it is used later to speed up the computation.

$existingSequence = {0 => 1, 1 => 2}


def fib(n)
  if $existingSequence.has_key? n
    return $existingSequence.values_at n;
  end

  if n == 0
    return 1;
  elsif n == 1
    return 2;
  end

  $existingSequence[n] = fib(n - 1) + fib(n - 2)
  return $existingSequence[n];
end

n = fib(2)
puts n

I expect this code to output 3 since that makes a call to fib(1) and fib(0) which returns 2 and 1 respectively, and then开发者_开发技巧 added to be 3. But the output is 1 and 2.

Hash.values_at returns an array, so when the code does fib(1) + fib(0), it's concatenating the arrays [2] and [1] together, resulting in the answer [2, 1]. Instead of:

return $existingSequence.values_at n;

...you should do this instead:

return $existingSequence[n]

BTW, the Fibonacci sequence traditionally starts with 0 and 1, not 1 and 2.

Slightly off-topic, here's a fun way of doing essentially the same thing, but using the Hash default value mechanism to use the Hash not only for caching, but also for computing the values:

fibs = { 0 => 0, 1 => 1 }.tap do |fibs|
  fibs.default_proc = ->(fibs, n) { fibs[n] = fibs[n-1] + fibs[n-2] }
end

fibs[9]
# => 34

Note: I didn't come up with this myself, I stole it from here.

The second line of fib should read:

return $existingSequence[n]

instead of

return $existingSequence.values_at n

Add puts $existingSequence to the end of the file to see the difference.