Ruby Fibonacci algorithm

Question

The following is a method I wrote to calculate a value in the Fibonacci sequence:

def fib(n)

    if n == 0
        return 0
    end
    if n == 1
        return 1
    end

    if n >= 2
        return fib(n-1) + (fib(n-2))
    end

end

It works uptil n = 14, but after that I get a message saying the program is taking too long to respond (I'm using repl.it). Anyone know why this is happening?

well, do you have to use recursive functions? I think your program overflows. — sertsedat, Jun 26 '14 at 19:32

Uri Agassi · Accepted Answer · 2017-01-10T10:44:32.210

23

Naive fibonacci makes a lot of repeat calculations - in fib(14) fib(4) is calculated many times.

You can add memoization to your algorithm to make it a lot faster:

def fib(n, memo = {})
  if n == 0 || n == 1
    return n
  end
  memo[n] ||= fib(n-1, memo) + fib(n-2, memo)
end
fib 14
# => 377
fib 24
# => 46368
fib 124
# => 36726740705505779255899443

edited Jan 10 '17 at 10:44

answered Jun 26 '14 at 19:40

Uri Agassi

36,848
14
76
93

I have dreamed about that and Ruby makes it possible. – Casimir et Hippolyte Jun 26 '14 at 19:45
1

Very elegant, nice job. – pjs Jun 26 '14 at 19:58
3

this called not caching but memoization instead – Anatoly Oct 03 '15 at 20:20
This method seems to return the number after the one you want. fib(5) should return 3 and not 5 which is the number after. – JCC Mar 19 '20 at 21:54
@JCC - like everything in computing - this was implemented as a zero based vector, meaning the first element is `fib(0)`. This means that `fib(5)` retrieves the _6th_ element in the list... – Uri Agassi Mar 20 '20 at 10:08
@UriAgassi What would we have to do to make it start on fib(1)? – JCC Mar 21 '20 at 13:58
@JCC - that's a great question - give it a try! see if you can make the minimal change to enable this - remember to check rigorously (including edge cases!) – Uri Agassi Mar 22 '20 at 08:12

pjs · Answer 2 · 2014-06-26T21:37:19.907

As others have pointed out, your implementation's run time grows exponentially in n. There are much cleaner implementations.

Constructive [O(n) run time, O(1) storage]:

def fib(n)
  raise "fib not defined for negative numbers" if n < 0
  new, old = 1, 0
  n.times {new, old = new + old, new}
  old
end

Memoized recursion [O(n) run time, O(n) storage]:

def fib_memo(n, memo)
  memo[n] ||= fib_memo(n-1, memo) + fib_memo(n-2, memo)
end

def fib(n)
  raise "fib not defined for negative numbers" if n < 0
  fib_memo(n, [0, 1])
end

Recursive powers of a matrix multiplication using squared halving of the power for when you just gotta know really big factorials like 1_000_000.fib [O(log n) run time and storage (on stack)]:

def matrix_fib(n)
  if n == 1
    [0,1]
  else
    f = matrix_fib(n/2)
    c = f[0] * f[0] + f[1] * f[1]
    d = f[1] * (f[1] + 2 * f[0])
    n.even? ? [c,d] : [d,c+d]
  end
end

def fib(n)
  raise "fib not defined for negative numbers" if n < 0
  n.zero? ? n : matrix_fib(n)[1]
end

score 3 · Answer 3 · edited May 23 '17 at 12:18

Your program has exponential runtime due to the recursion you use.

Expanding only the recursive calls a few levels to show you why:

fib(14) = fib(13) + fib(12)
        = (fib(12) + fib(11)) + (fib(11) + fib (10))
        = (((fib(11) + fib(10)) + (fib(10) + fib(9))) (((fib(10) + fib(9)) + (fib(9) + fib(8)))
        = ... //a ton more calls

The terrible runtime might be causing your program to hang, as increasing fib(n) by 1 means you have a TON more recursive calls

sertsedat · Answer 4 · 2020-08-11T20:31:01.237

2

your program overflows as Kevin L explained.

instead, you can use an iterative algorithm like this:

def fib (n)
  return 0 if n == 0
  return 1 if n == 1 or n == 2

  x = 0
  y = 1

  (2..n).each do
    z = (x + y)
    x = y
    y = z
  end

  return y
end

(0..14).map { |n| fib(n) }
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

edited Aug 11 '20 at 20:31

answered Jun 26 '14 at 19:36

sertsedat

3,490
1
25
45

Your code does not run by the way, there should not be an `end` after the `if` before the `else`, and `range` is not valid either. I will edit your code to make it work, revert / adjust if you disagree. – Daniël Knippers Jun 26 '14 at 19:46
well, I just wrote it with a sleepy head, I would appreciate the edit. – sertsedat Jun 26 '14 at 19:47
The Fibonacci series is: 0, 1, 1, 2, 3, 5, 8, 13, 21.... Your algorithm is not producing the correct result. For example, for the 20th element in the fibonacci series it returns 10946 instead of 6765; it's doing an extra iteration. Also, it should return 1 when the input is 2. To fix these issues, the range shoud be `(2..n)` and you should add the line `return 1 if n == 2`. I like your algorithm though. – Pablo Aug 11 '20 at 06:49

score 1 · Answer 5 · edited May 23 '17 at 12:18

I tried comparing the run time of two fibonacci methods on repl.it

require 'benchmark'

def fib_memo(n, memo = {})
  if n == 0 || n == 1
    return n
  end
  memo[n] ||= fib_memo(n-1, memo) + fib_memo(n-2, memo)
end


def fib_naive(n)
  if n == 0 || n == 1
    return n
  end
  fib_naive(n-1) + fib_naive(n-2)
end

def time(&block) 
  puts Benchmark.measure(&block) 
end

time {fib_memo(14)}
time {fib_naive(14)}

Output

0.000000   0.000000   0.000000 (  0.000008)
0.000000   0.000000   0.000000 (  0.000099)

As you can see, the runtime is quite different. As @Uri Agassi suggested, use memoization. The concept is explained quite well here https://stackoverflow.com/a/1988826/5256509

Ruby Fibonacci algorithm

5 Answers5

Linked