Recursion depth limit for a fibonacci program in Python [duplicate]

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
– doctorlove, Commented Jul 20, 2018 at 15:05
Python has a max recursion depth limit. So either use no recursion, or increase the max recursion stackoverflow.com/questions/8177073/… . But the second option is highly un-recommanded — T.Nel
– T.Nel, Commented Jul 20, 2018 at 15:06
You can change the stack size (stackoverflow.com/questions/3323001/…) or don't use a recursive solution. — Paul Hankin
– Paul Hankin, Commented Jul 20, 2018 at 15:06
@PaulHankin the problem here is not how to write the sequence but how to deal with the recursion depth issue. — ashr
– ashr, Commented Jul 20, 2018 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, it's easy to translate to Python and I had just finished doing so when this question got closed. — pjs
– pjs, Commented Jul 20, 2018 at 15:37

cs95 · Accepted Answer · 2018-07-20 15:24:30Z

3

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.

edited Jul 20, 2018 at 15:24

cs95

406k106 gold badges744 silver badges797 bronze badges

answered Jul 20, 2018 at 15:15

032407

613 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Recursion depth limit for a fibonacci program in Python [duplicate]

1 Answer 1

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Linked

Related