Recursion limits in Python

Why this matters

Many algorithms call themselves. A tree search, a flood fill or a divide-and-conquer sort can each be written as a function that calls itself on smaller pieces of the problem. This style is called recursion. It is often the shortest way to write the code, and it is often the clearest. Each call waits for the calls it makes, so the program keeps a record of every call that has started and not yet finished.

That record has a limit. Python sets a maximum depth for the record, and when the calls go deeper than the limit, the program stops with a RecursionError. This lesson shows how deep recursion uses the record, how to find the limit, what the error looks like, and what to do when a function needs more depth than the limit allows.

The stack and heap lesson earlier in this module introduced the call stack as the place where local names live. This lesson looks at the limit on that place, not at where objects are kept.

By the end you should be able to explain why a recursive function can work for 900 calls and fail for 1000, read the Python error output, and rewrite a deep recursive function as a loop.

The call stack, a stack of plates

Every running Python program has a call stack. Each time a function is called, the interpreter puts a new frame on top of the stack. A frame holds the function's parameters, its local names and a note of where to return when the function finishes. When the function returns, its frame is removed.

A cafeteria tray stack is a good picture. Each time someone calls a function, a plate is placed on the pile. Each time a function returns, the top plate is taken away. The pile has a limit on its height. If the pile grows past that height, the interpreter refuses to add another plate.

Python keeps a count of the frames on the stack. The limit is a setting, and you can read it with sys.getrecursionlimit(). The default is 1000. The limit counts frames, not bytes, so a function with many local names uses the same number of frames as a function with a few. That is different from the C and Java stacks, where a big frame uses more of the limited space.

Following the stack by hand

Take the call total(3) from example 2, where total(n) returns n + total(n - 1) and stops at total(0). Trace what is on the stack at each step.

• The program calls total(3). The stack holds one frame. It cannot finish yet, because it needs the value of total(2).
• total(3) calls total(2). The stack holds two frames: total(3) at the bottom and total(2) on top.
• total(2) calls total(1), which calls total(0). The stack now holds four frames.
• total(0) hits the base case and returns 0. Its frame is removed. total(1) finishes with 1 + 0 = 1, and its frame is removed.
• total(2) finishes with 2 + 1 = 3, and total(3) finishes with 3 + 3 = 6.

At its peak, total(3) needed four frames at the same time. Every one of those calls was on the stack together at the deepest point. For total(100000) the peak is 100001 frames, all present at once. That is why the depth of the recursion, not the total number of calls over time, decides whether the program fits under the limit.

Example 1: counting how deep we can go

The simplest recursive function calls itself with no stop condition. Each call adds one frame, and nothing ever removes one. The program below counts the calls and catches the error when the limit is reached. The catch lets the program print the count and continue.

Type nothing into the Input box for this program.

RecursionError caught at depth 999
message: maximum recursion depth exceeded

The depth is 999 rather than 1000, because the module's own code is already one frame on the stack, and the limit counts that frame too. The count is the same on every run of one Python version. The number depends on the Python version, so check it on your own version if you need the exact value.

The word global tells Python that depth is the name at module level, not a new name inside the function. Without it, the line depth += 1 would fail with an UnboundLocalError, as lesson 1 explained.

Example 2: a recursive sum

Now a realistic function. The next program adds the numbers from 1 to n by calling itself once for each number. The stop condition is n == 0. That stop condition is called the base case: the point where the function returns without calling itself again.

Type nothing into the Input box for this program.

limit: 1000
total(900) = 405450
total(1000) failed: maximum recursion depth exceeded

The first call works because its depth fits under the limit. The second needs about 1000 frames, which is more than the limit allows, so the function raises RecursionError. The function is correct. It simply asks for more depth than the interpreter allows by default.

The same result can be written as a loop, which uses one frame for the whole function, however large n is:

Type nothing into the Input box for this program.

5000050000

The loop gives the answer for 100,000 at once, and it would give the answer for a million without a limit problem, because a loop does not add frames. The result is larger than a 32-bit integer can hold, but Python integers have no fixed size, so the answer is exact. Other languages with fixed-size integers would need a wider type here.

Example 3: changing the limit

The limit is a setting, so a program can change it with sys.setrecursionlimit. Raising the limit lets the function go deeper. The next program raises the limit to 2000 and runs the same sum with 1500 calls.

Type nothing into the Input box for this program.

limit now: 2000
total(1500) = 1125750

This works, but the limit is not free. Each frame uses memory and stack space in the interpreter, and CPython also uses the C stack, the memory that the interpreter's own C code uses, to run the calls. A very high limit can let a recursion go so deep that the C stack runs out first, and then the process crashes instead of raising RecursionError. For that reason, raise the limit only by a small amount, and only when you have checked the depth you need.

A program that needs real depth has a better option. It can run the work in a thread, a separate line of execution inside the program, with a bigger stack. The threading.stack_size function sets the stack size for threads created after the call. The next program runs total(100000) in such a thread. It sets the recursion limit inside the thread and stores the result.

Type nothing into the Input box for this program.

{'value': 5000050000}

A large thread stack reserves more memory, so use it only for the work that needs it. The loop from example 2 is almost always the better choice, because it needs no special thread and no change to the limit. Use the thread only when the recursive form is much clearer, and the depth is known.

What an uncaught error looks like

If nothing catches the error, Python prints a traceback, the list of calls that were running when the error happened, and ends the program. This program recurses with no catch:

def forever(n):
    return forever(n + 1)
 
forever(0)

The output begins and ends like this. The file path and the number of repeated lines will differ on your machine:

Traceback (most recent call last):
  File "/home/you/recurse.py", line 4, in <module>
    forever(0)
    ~~~~~~~^^^
  File "/home/you/recurse.py", line 2, in forever
    return forever(n + 1)
  File "/home/you/recurse.py", line 2, in forever
    return forever(n + 1)
  File "/home/you/recurse.py", line 2, in forever
    return forever(n + 1)
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

Python does not print every frame. It prints the first few, then a line that says how many identical lines were left out. The last line gives the error type and the message. The repeated line, return forever(n + 1), is the line that keeps calling itself. Open it and ask what stops the calls. The traceback shows where the recursion is, which is usually enough to find the missing base case.

What happens in other languages

In C and C++, a stack that is too deep is not checked on each call. The program simply touches memory that it may not use, and the operating system stops it with a segmentation fault. The program gets no error it can catch. Java throws StackOverflowError, which can be caught, but its limit depends on the thread's stack size.

Python checks the depth on every Python function call, so normal code gets a RecursionError that it can catch. The one place where a crash can still happen is the case described in example 3, where the limit is raised so far that the C stack under the interpreter runs out first.

Common mistakes

A missing or wrong base case. The most common cause of this error is a recursion that never stops. If the check were n == 1 instead of n == 0, a call with n = 0 would never match it and would keep calling total(-1), total(-2) and so on forever. The limit is reached, and the error follows.

Catching the error in the middle of the work. RecursionError is raised at the deepest point of the recursion. If the function changes data as it goes, catching the error there can leave that data half done. Catch it at the top level, where you can report the failure, or where the data is safe to use.

Assuming the limit is a fixed number. The limit is a setting, and it can be changed. Students often write "the limit is 1000" in their notes, which is true only for the default. Read it with sys.getrecursionlimit() when the number matters.

Raising the limit instead of rewriting. A limit of one million lets a recursion go very deep, but the C stack can run out first, and the process crashes. The better fix is a loop, or a stack kept in a list, where the size is limited by memory and not by the recursion limit.

Using recursion for input that can be very large. A linked list with a million nodes walked by a recursive function needs a million frames. This is the case where a loop is the right tool. The sum_list function in the cache locality lesson is a loop for this reason.

Practice

Exercise 1. Write a recursive function count_down(n) that prints n, then n - 1, down to 1. Then say what happens if the base case is missing and you call count_down(3).

Show the answer

def count_down(n):
    if n == 0:
        return
    print(n)
    count_down(n - 1)

Without the base case, the function keeps calling count_down(n - 1). The numbers go down past zero into negative values, and the function never returns. Each call adds a frame, so the program ends with a RecursionError once the limit is reached.

Exercise 2. The total function fails for n equal to 1000 with the default limit. Rewrite it as a loop that gives the same result for every n.

Show the answer

def total(n):
    result = 0
    for i in range(1, n + 1):
        result += i
    return result

The loop uses one frame for the whole function, however large n is. For n equal to 100000, the result is 5000050000, the same as the recursive version with a larger limit.

Exercise 3. Predict the output of this program, then say why it prints what it does.

depth = 0
 
def recurse():
    global depth
    depth += 1
    if depth == 10:
        return
    recurse()
 
recurse()
print(depth)

Show the answer

It prints 10. The base case is depth == 10, so the function returns after ten calls, long before the limit is reached. Every call returns in turn, and the last line prints the final value of depth. No error is raised.

Exercise 4. A function is written recursively and it works for a list of 500 items but fails for 500,000 items. Describe two different fixes, and say what each one costs.

Show the answer

The first fix is to raise the limit with sys.setrecursionlimit. This is quick and changes nothing in the function's logic. It costs memory for every frame, and it only moves the limit. A list of 500,000,000 items would still fail, and a limit that is too high can crash the process when the C stack runs out. The second fix is to rewrite the function as a loop, or to keep a list of pending work and process it in a loop. This removes the limit on the call depth, because the pending work lives in a list in memory. It costs a rewrite, and for some problems, such as tree walks, the loop is less direct to read.

Exercise 5. Look at this function. What will happen when it runs, and what decides how many calls it makes before the error?

def walk(n):
    a = n
    b = n * 2
    walk(n + 1)

Show the answer

It has no base case, so it calls itself forever, and every call adds a frame. The program ends with a RecursionError once the limit is reached, which is 1000 by default. The two local names do not change that number, because the limit counts frames, not the size of the locals. The missing base case is the cause of the error.

Summary

• Each call adds a frame to the call stack, and the interpreter allows a fixed number of frames at once.
• The limit is sys.getrecursionlimit(), which is 1000 by default. The limit counts frames, not bytes.
• A full stack raises RecursionError, which can be caught. Without a catch, Python prints a traceback that repeats the recursive line.
• Raising the limit moves the point of failure but does not remove it, and a high limit can crash the process.
• A loop, or a list that holds the pending work, removes the limit for large inputs.