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

Question

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.

Claw · Accepted Answer · 2011-02-06 06:10:14Z

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.

answered Feb 6, 2011 at 6:10

Claw

7771 gold badge8 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Jörg W Mittag · Accepted Answer · 2011-02-06 16:03:08Z

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.

answered Feb 6, 2011 at 16:03

Jörg W Mittag

371k79 gold badges457 silver badges666 bronze badges

Comments

Michelle Tilley · Accepted Answer · 2011-02-06 06:11:34Z

1

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.

answered Feb 6, 2011 at 6:11

Michelle Tilley

159k40 gold badges379 silver badges312 bronze badges

Collectives™ on Stack Overflow

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

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related