Recursion depth limit for a fibonacci program in Python

Question

I have a Python program that performs pretty fast for fibonacci sequences up to 999. For numbers above 999, the program fails with RecursionError: maximum recursion depth exceeded in comparison. I am utilizing memoization to cache fibonacci of previous values.

Here is my code.

            def fibonacci(position, cache=None):
                if cache is None:
                    cache = [None] * (position + 1)

                if cache[position] is not None:
                    return cache[position]

                else:
                    if position < 3:
                        return 1
                    else:
                        cache[position] = fibonacci(position - 1, cache) + fibonacci(position - 2, cache)

                return cache[position]

Does anyone have a hint how I can improve my solution?

There's a closed form solution that therefore doesn't need recursion. You could iterate instead. Are you determined to recurse? — doctorlove, Jul 20 '18 at 15:05
Python has a max recursion depth limit. So either use no recursion, or increase the max recursion https://stackoverflow.com/questions/8177073/python-maximum-recursion-depth-exceeded . But the second option is highly un-recommanded — T.Nel, Jul 20 '18 at 15:06
You can change the stack size (https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it/18649326) or don't use a recursive solution. — Paul Hankin, Jul 20 '18 at 15:06
@PaulHankin the problem here is not how to write the sequence but how to deal with the recursion depth issue. — ashr, Jul 20 '18 at 15:12
You can do it representing the Fibonacci function in matrix form, then usin efficient matrix multiplication by halving the power and squaring. This makes the recursion stack O(log n) rather than O(n). [Here's the solution in Ruby](https://stackoverflow.com/questions/24438655/ruby-fibonacci-algorithm/24439070#24439070), it's easy to translate to Python and I had just finished doing so when this question got closed. — pjs, Jul 20 '18 at 15:37

score 3 · Accepted Answer · edited Jul 20 '18 at 15:24

There is a much easier solution which avoids recursion:

def fibonacci(position):
    if position < 3:
        return 1
    i = 3
    last1 = 1
    last2 = 1
    while i <= position:
        result = last1 + last2
        last2 = last1
        last1 = result
        i+=1
    return result

This stores the previous two values and adds them to produce a result, then replaces the last two with the result and the last value.

Recursion depth limit for a fibonacci program in Python

1 Answers1