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?
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
fib(0). This means that fib(5) retrieves the 6th element in the list...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
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
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
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]
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.
(2..n) and you should add the line return 1 if n == 2. I like your algorithm though.