Runtimeerror: maximum number of recursive calls exceeded - python

Question

fibonacci_cache = {}
def fibonacci(n):
    if n in fibonacci_cache:
        return fibonacci_cache[n]

    if n==1:
        value=1
    elif n==2:
        value=1
    elif n>2:
        value=fibonacci(n-1) + fibonacci(n-2)

fibonacci_cache[n]=value
return value

for n in (1,1000,91723):
    print (n,":",fibonacci(n))

Version of python:Python 2.7.10.

Returned this error to me: Runtimeerror: Maximum recursion Depth exceeded.

How do I solve this problem?

Answer 1

Python, by default, allows you to have a maximum depth equal to 1000 within the recursion; when this value is exceeded, the quoted error will be issued.

Runtimeerror: Maximum recursion Depth exceeded.

You can check the exact value on your server through the library sys, with the function getrecursionlimit:

import sys
print(sys.getrecursionlimit())

You can also change this value with the function setrecursionlimit:

sys.setrecursionlimit(2000)

The maximum value, according to the documentation, that you can set will depend on the platform limitations where you are running the code; and even if it is a very high value, there will always be a value that exceeds the maximum depth. There’s no way out of this with recursion.

However, a fairly simple solution is to calculate the Fibonacci sequence using a generator:

def fibonacci(n):
    a, b = 1, 1
    yield a
    for _ in range(1, n):
        a, b = b, a+b
        yield a

But as you have no interest in getting the sequence itself, but rather the nth sequence term, we can generate an iterator that will run through our generator in the interval we want, that is, in the nth term. We do this using the function islice library itertools:

import itertools

def nth_value(n):
    iterator = itertools.islice(fibonacci(n), n-1, None)
    return next(iterator)

Staying:

import itertools

def fibonacci(n):
    a, b = 1, 1
    yield a
    for _ in range(1, n):
        a, b = b, a+b
        yield a

def nth_value(n):
    return next(itertools.islice(fibonacci(n), n-1, n))

^{See working on Ideone | Repl.it | Wolfram Alpha}