Recursion in Python: a function that calls itself

Definition

Some problems are easier to describe in terms of themselves than as a sequence of steps. Computing the factorial of 5 amounts to computing 5 times the factorial of 4. Walking through a folder amounts to processing its files, then walking through each of its subfolders the same way. A plain loop does not fit that shape well: it expects to know in advance how many rounds it needs.

Recursion answers that need: a function calls itself, handles the share of the work that belongs to it, then passes the rest to a fresh copy of itself, until it lands on a case simple enough to be settled without delegating any further. On the factorial, this is what it looks like.

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))    # 120

Nothing in the syntax marks a recursive function: the def keyword is the same as anywhere else, it is the body that makes it recursive, by naming the function itself. Python simply executes the call it is asked to execute, without checking whether it points back to the running function or to another one.

The two legs it stands on

A function that calls itself takes a risk that a loop does not: if nothing stops it, it keeps going forever. A correct recursive function therefore always rests on two legs.

The word "strictly" matters more than it looks: a call fired on a problem of the same size runs forever, like an if whose condition would never change. Python then eventually raises a RecursionError somewhere around the thousandth call, and the traceback repeats the same line, a good clue that the base case is missing.

What the call stack really does

The hard part is not writing a recursive function, it is picturing what happens while it runs. Every call in progress takes a slot on the stack, with its own variables, released only once it finally hands a value back. Here is what that looks like for factorial(3).

factorial(3)
    3 * factorial(2)
        2 * factorial(1)
            1              # base case, the descent stops
        2 * 1 = 2
    3 * 2 = 6

The computation unfolds in two movements: a descent that piles up the pending calls, then a climb back that resolves them one by one. The first call is thus the last one to finish, and a recursive function uses memory in proportion to its depth, where a loop uses a fixed amount.

Recursion or loop: the real test

The choice is not a matter of personal taste, it follows the shape of the data being walked through: does the structure branch? The table below covers the most common cases.

On a flat list, recursion brings nothing and costs a stack for no reason: a plain walk does just as well. On a branching structure, it brings a great deal: the code matches the shape of the data, where an iterative walk would force you to keep a stack of pending items by hand.

The trap of computing the same thing a thousand times

A perfectly correct recursive function can still be catastrophically slow. The textbook case is the Fibonacci sequence written without care: every call fires two more, and the same values end up recomputed a number of times that explodes with depth.

def fibo(n):
    if n < 2:
        return n
    return fibo(n - 1) + fibo(n - 2)

fibo(35)    # several seconds of waiting

The fix does not touch the algorithm: it remembers the results already obtained, so they are never recomputed again. The lru_cache decorator, shipped by the functools module of the standard library, takes care of it in a single added line.

from functools import lru_cache

@lru_cache(maxsize=None)
def fibo(n):
    if n < 2:
        return n
    return fibo(n - 1) + fibo(n - 2)

fibo(35)    # instant

The gain is measured in orders of magnitude for a single added line. As soon as a recursive function calls itself more than once per level, as fibo does here, it almost always revisits the same values: checking whether memoisation applies becomes the first reflex to reach for.

Frequently asked questions

For equal work, yes, slightly: every call costs the creation of an execution context, where a loop round costs nothing of the sort. The gap stays small and never justifies twisting a tree walk to force it into a loop. What really costs dearly is the work redone several times without memoisation.

Yes, that is called mutual recursion: a base case somewhere in the cycle, and every round shrinking the problem. It is harder to spot, since taken alone, each function looks perfectly reasonable.

Print the depth alongside the arguments, using a level parameter raised on every call and an indentation that follows it. The trace shows the descent and the climb back on a single page, and the faulty base case stands out there far faster than by stepping through a debugger line by line.