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

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

import sys
sys.setrecursionlimit(1500)

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

    def __enter__(self):
        self.old_limit = sys.getrecursionlimit()
        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.

P.S. You may also want to increase the stack size of the Python process for big values of the recursion limit. That can be done via the ulimit shell builtin or limits.conf(5) file, for example.

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().

resource.setrlimit(resource.RLIMIT_STACK to increase Linux process stack size is also needed on Python <= 3.10

It apparently stopped mattering on Python 3.11, in which only the sys.setrecursionlimit matters:

sys.setrecursionlimit(2**31 - 1)

I choose 2**31 - 1 as that is the maximum value accepted by sys.setrecursionlimit on my system, anything larger blows up a:

OverflowError: Python int too large to convert to C int

Accoding to my experiments below, the change seems to have happened on Python 3.11. This is alsmost certainly an outcome of the "Faster CPython" project, 3.11 release notes mentions:

Inlined Python function calls

During a Python function call, Python will call an evaluating C function to interpret that function’s code. This effectively limits pure Python recursion to what’s safe for the C stack.

In 3.11, when CPython detects Python code calling another Python function, it sets up a new frame, and “jumps” to the new code inside the new frame. This avoids calling the C interpreting function altogether.

Most Python function calls now consume no C stack space, speeding them up.

Consider the following test code:

main.py

import resource
import sys

recursionlimit0 = sys.getrecursionlimit()
print('sys.getrecursionlimit() = {}'.format(sys.getrecursionlimit()))
print('resource.getrlimit(resource.RLIMIT_STACK) = {}'.format(resource.getrlimit(resource.RLIMIT_STACK)))

# Will segfault without in a few seconds this line.
if len(sys.argv) > 1:
    sys.setrecursionlimit(2**31 - 1)
if len(sys.argv) > 2:
    resource.setrlimit(resource.RLIMIT_STACK, [0x10000000, resource.RLIM_INFINITY])

print('sys.getrecursionlimit() = {}'.format(sys.getrecursionlimit()))
print('resource.getrlimit(resource.RLIMIT_STACK) = {}'.format(resource.getrlimit(resource.RLIMIT_STACK)))

def f(i):
    if i < 100000 or i % 100000 == 0:
        print(i)
    sys.stdout.flush()
    f(i + 1)
f(0)

this are the outcomes on the different test systems. Older Ubuntu were tested under Docker on Uubntu 25.04:

TODO: prior to 3.11, after increasing the process stack, what is the next limit that leads to segfault and prevents OOM as desired?

Further explanation of the Linux process stack limit

The Linux kernel limits the stack of processes.

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

Certain versions of Python seem to store some data that is used during recursion on the stack of the interpreter. This old thread: CPython - Internally, what is stored on the stack and heap? suggests that Python objects are not stored on the stack, heap only, which implies that resource.setrlimit(resource.RLIMIT_STACK should not matter. However our experiments indicate that the answers on that thread are not entirely correct.

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.

From Bash, you can see and set the stack limit (in kb) by running the following commands before launching Python:

ulimit -s
ulimit -s 10000

The default value for me is 8 MB.

If we manage to increase all relevant limits correctly as desired, the interpreter will take more and more RAM until it takes up all the system RAM, a thich point the Linux OOM Killer will be called in to kill some processes and free memory.

See also:

• Setting stacksize in a python script
• What is the hard recursion limit for Linux, Mac and Windows?

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

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.)

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.

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.

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.

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

RecursionError: maximum recursion depth exceeded in comparison

Solution :

First it’s better to know when you execute a recursive function in Python on a large input ( > 10^4), you might encounter a “maximum recursion depth exceeded error”.

The sys module in Python have a function getrecursionlimit() can show the recursion limit in your Python version.

import sys
print("Python Recursive Limitation = ", sys.getrecursionlimit())

The default in some version of Python is 1000 and in some other it was 1500

You can change this limitation but it’s very important to know if you increase it very much you will have memory overflow error.

So be careful before increase it. You can use setrecursionlimit() to increase this limitation in Python.

import sys
sys.setrecursionlimit(3000)

Please follow this link for more information about somethings cause this issue :

https://elvand.com/quick-sort-binary-search/

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

Edit: 6 years later I realized my "Use generators" was flippant and didn't answer the question. My apologies.

I guess my first question would be: do you really need to change the recursion limit? If not, then perhaps my or any of the other answers that don't deal with changing the recursion limit will apply. Otherwise, as noted, override the recursion limit using sys.getrecursionlimit(n).

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 Introduction to Python Generators.

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)

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.

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))

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)

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))