A Python function with unbounded recursion. It raises a
RecursionError when called:
RecursionError. The error is that the recursion is unbounded. How does Python know what caused the error?
According to the docs,
RecursionError “is raised when the interpreter detects that the maximum recursion depth (see
sys.getrecursionlimit()) is exceeded.”
The “maximum recursion depth” is 1000. What if the call stack reaches that limit without recursion? Has anyone ever done this real life? I haven’t. Here’s a function to set up an artificial example:
Run that function and you’ll get a file like this:
f1 builds the stack to depth 1, calling
f2 builds it to depth 2, and calling
f999 builds it to depth 999.
f1000 builds the stack to depth 1000. You won’t believe what happens next.
RecursionError: maximum recursion depth exceeded. But there was no recursion! It would be more accurate to say
StackLimitError: maximum call stack depth exceeded.
f1000 will run just fine if the “maximum recursion depth” (really, the maximum call stack depth) is adjusted:
Exercises for the reader
- Find a real-life example of the default stack limit getting hit without recursion.
- Do something interesting with the function
You deserve something special for having read this far. Here’s a trick that experienced Python programmers use to optimize their unboundedly recursive functions. Recall the definition of
Now take a look at the bytecode of
f using the
dis function from the
A Python function with no explicit return value will return
None. That’s the case with
f. It calls itself, then discards the return value and loads and returns
None. But we know that
None, so that’s two wasted instructions. A variation of
f tightens up the bytecode:
LOAD_CONST instructions are skipped by returning the value of the recursive call straightaway.
g() will result in a
RecursionError just the same as
f(), but it will do so a little more efficiently.