RecursionError (Python)

In short: A function calls itself too often without stopping; Python aborts at about 1000 levels.

In more detail: Message: RecursionError: maximum recursion depth exceeded. Each function call occupies space on the call stack. Python limits the depth (default about 1000) to prevent a crash. It is the Python counterpart to Java’s StackOverflowError.

In Depth

Possible causes

• Missing or wrong base case: the recursion has no end.
• The step does not lead towards the base case (for example n does not get smaller).
• Mutual recursion between two functions.
• Very deep but legitimate recursion (long lists, trees, deep graphs).
• A method unintentionally calls itself through __getattr__/property.

Example

def factorial(n):
    return n * factorial(n - 1)   # base case missing!
 
def factorial(n):
    if n <= 1:                    # base case
        return 1
    return n * factorial(n - 1)

Solutions

1. Check the base case: is it reached every time?
2. Work with a loop and own stack instead of recursion (iterative).
3. Tail recursion is not optimised by Python; rebuild manually.
4. For legitimate deep recursion set sys.setrecursionlimit(10000) (carefully, crash risk) or switch to iteration.
5. Memoisation (functools.lru_cache) avoids repeated calls but does not solve a depth problem.
6. Print the arguments with print and check how they change.

See also: StackOverflowError, Recursion, Stack and heap