RecursionError in Python: recursion that never stops

Definition

You write a function that calls itself, run it, and instead of a result you get a wall of text repeating the same line hundreds of times. That is a RecursionError: the function called itself too many times without ever handing control back.

Python keeps track of each call still in progress, much like a stack of plates that can only be cleared from the top. That stack has a maximum height, set by default at around one thousand calls. The thousandth call that has still not handed control back triggers the error.

Here is the plainest version of the problem, a function with no stopping condition at all:

def count(n):
    return count(n - 1)

count(5)

# RecursionError: maximum recursion depth exceeded

The message says almost nothing: it names no offending value, unlike a KeyError, which shows the missing key, or a ValueError, which shows the rejected value. The useful information sits in the traceback that comes with it.

The stopping case, the only real cause

Faced with this wall of identical lines, the question to ask is always the same: where does the descent stop? A recursive function stands on two legs: the base case hands back a value without calling itself again, the recursive case does call itself, but on a smaller problem, which moves things closer to that exit on every round. As soon as one of the two is missing, or written wrong, nothing stops the calls.

A factorial shows the balance between the two well:

def factorial(n):
    if n <= 1:
        return 1                   # base case: the exit
    return n * factorial(n - 1)    # recursive case: moves toward the exit

In practice, almost every case comes down to one of three mistakes. The first is a base case that simply does not exist: no if ever cuts the descent short. The second is a base case that is present but unreachable, because the argument never shrinks, or steps clean over the stopping value: n - 2 applied to an odd number will never touch zero. The third is a base case placed after the recursive call, so it only gets evaluated once the descent is over, which is to say never.

Reading a thousand-line traceback

A recursion traceback is discouraging before it is even read: hundreds of lines that all look alike scroll past on the screen. It actually reads in three seconds, once you know where to look: the first lines name the original call, the last ones name the function going round in circles. The middle is nothing but the same handful of lines copied up to the ceiling, and it can be skipped.

The pattern repeating in that middle section is a good clue to the cause:

The last two cases often come as a surprise, because no recursive call appears anywhere in the code you actually wrote. The __getattr__ method is called whenever a requested attribute cannot be found: if its own body reads an attribute of self that does not exist either, it ends up calling itself. Mutual recursion follows the same logic, more quietly still: each of the two functions looks perfectly sound read on its own.

Raising the limit rarely fixes the problem

Faced with this error, the most common reflex is to push the ceiling up and move on.

import sys

sys.setrecursionlimit(10000)

On a genuinely endless recursion, that line changes almost nothing, other than delaying the exception by a few calls, and sometimes making things worse.

Raising the limit is justified in exactly one situation: a correct algorithm applied to genuinely deep data, such as a category tree nested hundreds of levels down. The function is not at fault, it is simply deeper than the default stack allows. Everywhere else, the right answer is to turn the descent into a loop, with a list kept by hand playing the part of the stack. The code often reads better for it, and stops having a maximum depth at all.

Frequently asked questions

Because the recursion depth follows the size of the data, not how complex it looks. A tree two hundred levels deep gets through, a tree twelve hundred levels deep goes past the default ceiling. The function itself is not wrong: it is simply deeper than the stack allows, and that is the sign that an iterative rewrite is called for.

No, but it is worth knowing that it gets no special optimisation. Unlike other languages, Python does not eliminate tail calls: every call really does take up a slot on the stack. Recursion keeps its full value on tree-shaped structures, where it makes the code more readable than a loop would. It becomes more questionable on a plain linear walk, which a while loop handles without a depth limit.

A print of sys.getrecursionlimit() shows the active value, one thousand on most installations. But that says nothing about the depth a given function actually reaches. Counting it directly is often more telling, and the Python course shows how to instrument a function and watch it descend call after call.