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?

Answer 1

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