Python Recursion

Intermediate

A recursive function calls itself to solve a problem by reducing it to a smaller version of the same problem. Recursion works because an ordinary function call can invoke the same function again; each call has its own local state.

The two parts of a recursive function

A useful recursive definition has two parts: a base case that can be answered directly, and a recursive case that moves the input toward that base case.

Here, zero is the base case. Every other call makes the next problem smaller by subtracting one.

Give every call a way to stop

Without a base case, recursive calls keep creating more calls until Python detects that the maximum recursion depth has been exceeded. RecursionError is raised in that situation.

The recursive case changes n to n - 1. Eventually the call reaches zero, returns one, and the waiting calls can finish their multiplications.

The recursive call does not replace the current call

When one call invokes the same function, the earlier call pauses at that call expression. Its local variables remain associated with that invocation while the newer call runs.

The innermost call finishes first. Its returned value becomes part of the result computed by the call that made it, and the process continues outward.

Each call has its own local state

A recursive function does not make one local variable serve every invocation. Python creates a separate local namespace for each function call, so each call can have its own parameter values and local variables.

Recursion can describe nested data

Recursion is especially natural when the data itself can contain smaller structures of the same kind. The function below handles a nested list by treating a nested list as another problem of the same shape.

The recursive call is not needed because lists are special; it is useful because each nested list can be handled by the same rule.

Know the recursion limit

Python places a limit on recursion depth to prevent runaway recursion from overflowing the interpreter stack. The current limit can be inspected with sys.getrecursionlimit(), and exceeding the limit raises RecursionError.

Choose recursion deliberately

Recursion is a technique, not a requirement. It is a strong fit when a problem naturally contains smaller versions of itself, such as a tree or nested structure. For a simple linear repetition, a for or while loop is often easier to read and does not consume one recursive call per step.

Both versions compute the same total. The recursive version is useful for learning the pattern, but the loop is a simpler fit for this particular linear task.