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))
Python version: Python 2.7.10.
I got this error: RuntimeError: maximum recursion depth exceeded.
How do I solve this problem?
Python, by default, allows you to have a maximum depth equal to 1000 within the recursion; when this value is exceeded, the cited error will be issued.
RuntimeError: maximum recursion depth exceeded.
You can check the exact value on your server through the sys library, with the function getrecursionlimit :
import sys
print(sys.getrecursionlimit())
You can also change this value with setrecursionlimit function:
sys.setrecursionlimit(2000)
The maximum amount, 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 will exceed the maximum depth. There's no escaping it with recursion.
However, a very simple solution is to calculate the Fibonacci sequence through 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 obtaining the sequence itself, but rather the nth term of the sequence, we can generate an iterator that will run through our generator in the range we want, nth term. We do this using the islice function of the itertools :
import itertools
def nth_value(n):
iterator = itertools.islice(fibonacci(n), n-1, None)
return next(iterator)
Getting:
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 at Ideone | Repl.it | Wolfram Alpha