# What is the maximum recursion depth in Python, and how to increase it?

## The Question :

491 people think this question is useful

I have this tail recursive function here:

def recursive_function(n, sum):
if n < 1:
return sum
else:
return recursive_function(n-1, sum+n)

c = 998
print(recursive_function(c, 0))



It works up to n=997, then it just breaks and spits out a RecursionError: maximum recursion depth exceeded in comparison. Is this just a stack overflow? Is there a way to get around it?

• memoization could speed up your function and increase its effective recursive depth by making previously calculated values terminate instead of increasing the stack size.
• The recursion limit is usually 1000.
• @tonix the interpreter adds a stack frame (the line <n>, in <module> in stack traces) and this code takes 2 stack frames for n=1 (because the base case is n < 1, so for n=1 it still recurses). And I guess the recursion limit is not inclusive, as in it’s “error when you hit 1000” not “error if you exceed 1000 (1001)”. 997 + 2 is less than 1000 so it works 998 + 2 doesn’t because it hits the limit.
• @tonix no. recursive_function(997) works, it breaks at 998. When you call recursive_function(998) it uses 999 stack frames and 1 frame is added by the interpreter (because your code is always run as if it’s part of top level module), which makes it hit the 1000 limit.

558 people think this answer is useful

It is a guard against a stack overflow, yes. Python (or rather, the CPython implementation) doesn’t optimize tail recursion, and unbridled recursion causes stack overflows. You can check the recursion limit with sys.getrecursionlimit:

import sys
print(sys.getrecursionlimit())



and change the recursion limit with sys.setrecursionlimit:

sys.setrecursionlimit(1500)



but doing so is dangerous — the standard limit is a little conservative, but Python stackframes can be quite big.

Python isn’t a functional language and tail recursion is not a particularly efficient technique. Rewriting the algorithm iteratively, if possible, is generally a better idea.

143 people think this answer is useful

Looks like you just need to set a higher recursion depth:

import sys
sys.setrecursionlimit(1500)



58 people think this answer is useful

It’s to avoid a stack overflow. The Python interpreter limits the depths of recursion to help you avoid infinite recursions, resulting in stack overflows. Try increasing the recursion limit (sys.setrecursionlimit) or re-writing your code without recursion.

From the Python documentation:

sys.getrecursionlimit()

Return the current value of the recursion limit, the maximum depth of the Python interpreter stack. This limit prevents infinite recursion from causing an overflow of the C stack and crashing Python. It can be set by setrecursionlimit().

36 people think this answer is useful

If you often need to change the recursion limit (e.g. while solving programming puzzles) you can define a simple context manager like this:

import sys

class recursionlimit:
def __init__(self, limit):
self.limit = limit
self.old_limit = sys.getrecursionlimit()

def __enter__(self):
sys.setrecursionlimit(self.limit)

def __exit__(self, type, value, tb):
sys.setrecursionlimit(self.old_limit)



Then to call a function with a custom limit you can do:

with recursionlimit(1500):
print(fib(1000, 0))



On exit from the body of the with statement the recursion limit will be restored to the default value.

18 people think this answer is useful

resource.setrlimit must also be used to increase the stack size and prevent segfault

The Linux kernel limits the stack of processes.

Python stores local variables on the stack of the interpreter, and so recursion takes up stack space of the interpreter.

If the Python interpreter tries to go over the stack limit, the Linux kernel makes it segmentation fault.

The stack limit size is controlled with the getrlimit and setrlimit system calls.

Python offers access to those system calls through the resource module.

sys.setrecursionlimit mentioned e.g. at https://stackoverflow.com/a/3323013/895245 only increases the limit that the Python interpreter self imposes on its own stack size, but it does not touch the limit imposed by the Linux kernel on the Python process.

Example program:

main.py

import resource
import sys

print resource.getrlimit(resource.RLIMIT_STACK)
print sys.getrecursionlimit()
print

# Will segfault without this line.
resource.setrlimit(resource.RLIMIT_STACK, [0x10000000, resource.RLIM_INFINITY])
sys.setrecursionlimit(0x100000)

def f(i):
print i
sys.stdout.flush()
f(i + 1)
f(0)



Of course, if you keep increasing setrlimit, your RAM will eventually run out, which will either slow your computer to a halt due to swap madness, or kill Python via the OOM Killer.

From bash, you can see and set the stack limit (in kb) with:

ulimit -s
ulimit -s 10000



The default value for me is 8Mb.

Tested on Ubuntu 16.10, Python 2.7.12.

14 people think this answer is useful

Use a language that guarantees tail-call optimisation. Or use iteration. Alternatively, get cute with decorators.

9 people think this answer is useful

I realize this is an old question but for those reading, I would recommend against using recursion for problems such as this – lists are much faster and avoid recursion entirely. I would implement this as:

def fibonacci(n):
f = [0,1,1]
for i in xrange(3,n):
f.append(f[i-1] + f[i-2])
return 'The %.0fth fibonacci number is: %.0f' % (n,f[-1])



(Use n+1 in xrange if you start counting your fibonacci sequence from 0 instead of 1.)

9 people think this answer is useful

Of course Fibonacci numbers can be computed in O(n) by applying the Binet formula:

from math import floor, sqrt

def fib(n):
return int(floor(((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))+0.5))



As the commenters note it’s not O(1) but O(n) because of 2**n. Also a difference is that you only get one value, while with recursion you get all values of Fibonacci(n) up to that value.

8 people think this answer is useful

I had a similar issue with the error “Max recursion depth exceeded”. I discovered the error was being triggered by a corrupt file in the directory I was looping over with os.walk. If you have trouble solving this issue and you are working with file paths, be sure to narrow it down, as it might be a corrupt file.

6 people think this answer is useful

If you want to get only few Fibonacci numbers, you can use matrix method.

from numpy import matrix

def fib(n):
return (matrix('0 1; 1 1', dtype='object') ** n).item(1)



It’s fast as numpy uses fast exponentiation algorithm. You get answer in O(log n). And it’s better than Binet’s formula because it uses only integers. But if you want all Fibonacci numbers up to n, then it’s better to do it by memorisation.

4 people think this answer is useful

Use generators?

def fib():
a, b = 0, 1
while True:
yield a
a, b = b, a + b

fibs = fib() #seems to be the only way to get the following line to work is to
#assign the infinite generator to a variable

f = [fibs.next() for x in xrange(1001)]

for num in f:
print num



above fib() function adapted from: http://intermediatepythonista.com/python-generators

4 people think this answer is useful

We can do that using @lru_cache decorator and setrecursionlimit() method:

import sys
from functools import lru_cache

sys.setrecursionlimit(15000)

@lru_cache(128)
def fib(n: int) -> int:
if n == 0:
return 0
if n == 1:
return 1

return fib(n - 2) + fib(n - 1)

print(fib(14000))



### Output

3002468761178461090995494179715025648692747937490792943468375429502230242942284835863402333575216217865811638730389352239181342307756720414619391217798542575996541081060501905302157019002614964717310808809478675602711440361241500732699145834377856326394037071666274321657305320804055307021019793251762830816701587386994888032362232198219843549865275880699612359275125243457132496772854886508703396643365042454333009802006384286859581649296390803003232654898464561589234445139863242606285711591746222880807391057211912655818499798720987302540712067959840802106849776547522247429904618357394771725653253559346195282601285019169360207355179223814857106405285007997547692546378757062999581657867188420995770650565521377874333085963123444258953052751461206977615079511435862879678439081175536265576977106865074099512897235100538241196445815568291377846656352979228098911566675956525644182645608178603837172227838896725425605719942300037650526231486881066037397866942013838296769284745527778439272995067231492069369130289154753132313883294398593507873555667211005422003204156154859031529462152953119957597195735953686798871131148255050140450845034240095305094449911578598539658855704158240221809528010179414493499583473568873253067921639513996596738275817909624857593693291980841303291145613566466575233283651420134915764961372875933822262953420444548349180436583183291944875599477240814774580187144637965487250578134990402443365677985388481961492444981994523034245619781853365476552719460960795929666883665704293897310201276011658074359194189359660792496027472226428571547971602259808697441435358578480589837766911684200275636889192254762678512597000452676191374475932796663842865744658264924913771676415404179920096074751516422872997665425047457428327276230059296132722787915300105002019006293320082955378715908263653377755031155794063450515731009402407584683132870206376994025920790298591144213659942668622062191441346200098342943955169522532574271644954360217472458521489671859465232568419404182043966092211744372699797375966048010775453444600153524772238401414789562651410289808994960533132759532092895779406940925252906166612153699850759933762897947175972147868784008320247586210378556711332739463277940255289047962323306946068381887446046387745247925675240182981190836264964640612069909458682443392729946084099312047752966806439331403663934969942958022237945205992581178803606156982034385347182766573351768749665172549908638337611953199808161937885366709285043276595726484068138091188914698151703122773726725261370542355162118164302728812259192476428938730724109825922331973256105091200551566581350508061922762910078528219869913214146575557249199263634241165352226570749618907050553115468306669184485910269806225894530809823102279231750061652042560772530576713148647858705369649642907780603247428680176236527220826640665659902650188140474762163503557640566711903907798932853656216227739411210513756695569391593763704981001125



### Source

functools lru_cache

3 people think this answer is useful

As @alex suggested, you could use a generator function to do this sequentially instead of recursively.

Here’s the equivalent of the code in your question:

def fib(n):
def fibseq(n):
""" Iteratively return the first n Fibonacci numbers, starting from 0. """
a, b = 0, 1
for _ in xrange(n):
yield a
a, b = b, a + b

return sum(v for v in fibseq(n))

print format(fib(100000), ',d')  # -> no recursion depth error



2 people think this answer is useful

Many recommend that increasing recursion limit is a good solution however it is not because there will be always limit. Instead use an iterative solution.

def fib(n):
a,b = 1,1
for i in range(n-1):
a,b = b,a+b
return a
print fib(5)



2 people think this answer is useful

I wanted to give you an example for using memoization to compute Fibonacci as this will allow you to compute significantly larger numbers using recursion:

cache = {}
def fib_dp(n):
if n in cache:
return cache[n]
if n == 0: return 0
elif n == 1: return 1
else:
value = fib_dp(n-1) + fib_dp(n-2)
cache[n] = value
return value

print(fib_dp(998))



This is still recursive, but uses a simple hashtable that allows the reuse of previously calculated Fibonacci numbers instead of doing them again.

2 people think this answer is useful
import sys
sys.setrecursionlimit(1500)

def fib(n, sum):
if n < 1:
return sum
else:
return fib(n-1, sum+n)

c = 998
print(fib(c, 0))



0 people think this answer is useful

We could also use a variation of dynamic programming bottom up approach

def fib_bottom_up(n):

bottom_up = [None] * (n+1)
bottom_up[0] = 1
bottom_up[1] = 1

for i in range(2, n+1):
bottom_up[i] = bottom_up[i-1] + bottom_up[i-2]

return bottom_up[n]

print(fib_bottom_up(20000))



0 people think this answer is useful

I’m not sure I’m repeating someone but some time ago some good soul wrote Y-operator for recursively called function like:

def tail_recursive(func):
y_operator = (lambda f: (lambda y: y(y))(lambda x: f(lambda *args: lambda: x(x)(*args))))(func)
def wrap_func_tail(*args):
out = y_operator(*args)
while callable(out): out = out()
return out
return wrap_func_tail



and then recursive function needs form:

def my_recursive_func(g):
def wrapped(some_arg, acc):
if <condition>: return acc
return g(some_arg, acc)
return wrapped

# and finally you call it in code

(tail_recursive(my_recursive_func))(some_arg, acc)



for Fibonacci numbers your function looks like this:

def fib(g):
def wrapped(n_1, n_2, n):
if n == 0: return n_1
return g(n_2, n_1 + n_2, n-1)
return wrapped

print((tail_recursive(fib))(0, 1, 1000000))



output:

..684684301719893411568996526838242546875



(actually tones of digits)