Fibonacci sequence: Recursion depth excess

Question

Given the function to generate fibonacci numbers:

def fibonacci(x, memory = {0:0, 1:1}):
        if x not in memory:
                memory[x] = fibonacci(x-1, memory)+fibonacci(x-2, memory)
        return memory[x]

When I try some arbitrarily large number, say 4000th fibonacci number, I get an error:

RuntimeError: maximum recursion depth exceeded

What is the error caused by? What can be done as a work around without sacrificing the efficiency? I prefer this to iteration, since by iterating, calculating even the 50th position takes astronomically long for a computer (read: half a minute).

Iteration should significantly outperform recursion -- it doesn't sound right that it would take more than a smallish fraction of a second to compute F1 through F50. Anyway, if this is Python, then you might want to look at sys.getrecursionlimit() and sys.setrecursionlimit() — Jim Lewis, Dec 04 '14 at 06:25

score 2 · Answer 1 · answered Dec 04 '14 at 06:38

As the others have mentioned you have hit the stack memory limit. You usually have a maximum of 50-100 maximum nested recursive calls before you hit this limit.

I think you might have a misconception about iteration (unrolling recursive functions)

def fib():
    a=0
    b=1;
    c=1;
    for x in range(4000):
        c = a + b;
        a = b;
        b = c;
    print c;

fib();

There is no way this function would take longer than your recursive one.

score 1 · Accepted Answer · answered Dec 04 '14 at 06:59

Iteration is lot better than recursion in my opinion. Because

Iteration is lot more easily readable and traceable than recursion.
You can use concepts such as Generators to reduce the memory load that may not be feasible with recursive functions.

As for what is Recursion Limit, you can see here. It gives a basic explanation of what and why recursion limit is there. As shown there, you can give sys.setrecursionlimit to any value you desired.

Using iterator, this can be used for fibonacci series:

def fib(a, b):
    return b, a+b

for i in range(20):
    if i in (0, 1):
        print i
    else:
        print a
    a, b = fib(a, b)

score 0 · Answer 3 · edited May 23 '17 at 10:25

0

I think you hit the recursion limit. Here is a link to a similar post, which might help. I would recommend that you use iteration, but I also came across this code to increase the stack size, but have not tested it:

import sys
sys.setrecursionlimit(10000) # change the '10000' to something that works

edited May 23 '17 at 10:25

Community

1
1

answered Dec 04 '14 at 06:29

pietergdp

15
6

Fibonacci sequence: Recursion depth excess

3 Answers3