Recursion & the Call Stack

The problem

Some problems contain smaller copies of themselves. A factorial is n times a smaller factorial; a folder holds files and more folders; a JSON value can hold more JSON values; every subtree of a tree is a tree. A loop over that kind of structure has to remember by hand where it was and what is left to do. Recursion hands the bookkeeping to the language: the function answers the smallest case directly and passes everything else to a call of itself on a smaller input, and the runtime keeps each unfinished call on the call stack until its answer comes back.

That bookkeeping has a price. Every pending call holds a stack frame, the stack is finite, and a function that calls itself more than once can end up solving the same subproblem again and again.

How it works

Every recursive function needs two parts:

• a base case that returns an answer without recursing (if n <= 1: return 1), and
• a recursive case that calls the function on an input closer to the base case (fact(n - 1)) and builds its own answer from the result (n * fact(n - 1)).

To check a recursive function, don't trace every level. Check that the base case is right, then trust the smaller call: assume fact(n - 1) returns the right value and check that n * fact(n - 1) is then right for n. That is a proof by induction, and it is also the way to write the function in the first place. The other half of the argument is progress: every call must move toward the base case. Leave the base case out, or step over it (counting down by 2 toward a base case of exactly 0 from an odd number), and the calls never end.

At run time each call pushes a stack frame that holds the call's arguments and local variables, the work it still has to do once the inner call returns (the pending 4 × ? in the animation), and where to return: the point in the caller that carries on with the result. Only the newest frame runs; every frame below it is paused. When the base case returns, the stack unwinds: frames pop in reverse order, and each one finishes its own step with the value it gets back.

Recursion fits recursive data. A function that walks a tree, a nested list, a JSON document, a directory or a syntax tree has the same shape as the data, and its depth is the nesting depth of the data. Divide and conquer recurses on pieces of the input: merge sort and quicksort recurse on two parts, and binary search on one half, so their depth grows with log n rather than n (for quicksort, on average).

Recursion or a loop? Anything recursive can be written as a loop, and the other way round. A linear recursion such as fact, one call per step, reads just as well as a loop, and the loop needs one frame instead of n. Structure and Interpretation of Computer Programs (section 1.2.1) contrasts the two shapes: the recursive process builds a chain of deferred multiplications, while the iterative one carries its whole state in a fixed set of variables. Branching recursion, such as walking a tree or trying choices and backing out of them, is where recursion reads much better. To remove it, keep your own stack, a list you push to and pop from:

def total(items):                 # recursive: lists nested to any depth
    return sum(total(x) if isinstance(x, list) else x for x in items)

def total_iter(items):            # the same walk with an explicit stack
    result, stack = 0, [items]
    while stack:
        for x in stack.pop():
            if isinstance(x, list):
                stack.append(x)   # visit it later instead of recursing now
            else:
                result += x
    return result

print(total([1, [2, [3, 4]], 5]), total_iter([1, [2, [3, 4]], 5]))   # 15 15

The explicit stack lives on the heap, so it can grow as far as memory allows: on a list nested 10,000 deep, total_iter returns while total raises RecursionError. Python's own os.walk made the same switch in 3.12, so that very deep directory trees no longer hit the recursion limit (CPython issue 89727).

Tail calls. A call is a tail call when it is the last thing a function does (return f(x)). The caller has nothing left to do, so its frame could be reused, and a recursion made only of tail calls could run in constant stack space. Whether that happens depends on the language:

• Scheme requires it: the R7RS report (section 3.5) says implementations must be properly tail-recursive, which is what lets Scheme programs write loops as recursion.
• JavaScript specified proper tail calls in ECMAScript 2015, for strict-mode code only. Of the major engines only Safari's JavaScriptCore ships them; Chrome, Edge, Firefox and Node.js do not (compatibility table).
• Kotlin does it on request: a function marked tailrec that calls itself in tail position is compiled into a loop (Kotlin docs).
• Python does not, by design. Guido van Rossum argued that eliminating tail calls throws away the frames a traceback needs, and that code relying on it would break on any implementation without it. CPython 3.14's new tail-calling interpreter is a different thing: it changes how the interpreter's own C code moves between bytecode handlers, and the release notes state that tail calls in Python functions are still not optimized.

fact as written is not a tail call anyway, because the multiplication happens after the inner call returns. Passing the running product down (fact(n - 1, acc * n)) makes it one, but in Python that version still takes one frame per call, so the loop is the real fix there.

Memoization. Naive Fibonacci calls itself twice per call, and the two branches overlap: fib(5) computes fib(3) twice and fib(2) three times. Caching each result the first time it is computed turns the 242,785 calls of fib(25) into 26 distinct computations. In Python, functools.cache (3.9 and later) is an unbounded cache, the same as functools.lru_cache(maxsize=None); lru_cache on its own keeps the 128 most recent results by default. Filling the same table bottom-up, smallest subproblem first, is dynamic programming, and it removes the recursion as well.

Code

import functools

def fact(n):                      # n >= 0
    if n <= 1:                    # base case: answer directly
        return 1
    return n * fact(n - 1)        # recursive case: a smaller n

def fact_loop(n):                 # same result in one frame: O(1) extra space
    result = 1
    for k in range(2, n + 1):
        result *= k
    return result

calls = 0

def fib(n):                       # naive: every call makes two more
    global calls
    calls += 1
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

@functools.cache                  # remembers each answer the first time
def fib_memo(n):
    if n <= 1:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

print(fact(4), fact_loop(4))                        # 24 24
print(fib(25), calls)                               # 75025 242785
print(fib_memo(25), fib_memo.cache_info().misses)   # 75025 26

cache_info().misses counts the calls that had to compute a value: one for each n from 0 to 25. fact_loop(5000) returns a number with 16,326 digits, while fact(5000) raises RecursionError: maximum recursion depth exceeded. Run as a script on CPython 3.11, it gets as far as fact(4002): 999 frames of fact plus the module's own frame make 1000, the default limit. A REPL, a test runner or a debugger puts frames of its own beneath your code, so the exact depth varies.

Complexity

Each function does the same work for every input of a given size, so its best, average and worst cases coincide; stable and in place don't apply. Big-O Notation explains the notation. The table counts each multiplication or addition as one step. Python integers grow without bound (5000! has 16,326 digits), so for large n the arithmetic itself gets slower.

When to use it

• The data is recursive (trees, nested lists or JSON, file systems, syntax trees, grammars) and its depth is modest or bounded. A balanced binary tree with a million nodes is only about 20 levels deep.
• Divide and conquer, where each call works on a fraction of the input so the depth grows with log n: merge sort, binary search, and quicksort on average.
• Searching over choices (permutations, puzzles, parsing): the stack remembers which choice to undo next, which is the heart of backtracking.
• Not for long linear chains in a language without tail-call elimination. Processing a million-item list one element per call needs a million frames; use a loop.
• Not when untrusted input sets the depth, unless you cap it. A deeply nested JSON body or GraphQL query can exhaust the stack (see the implementation notes).

Trade-offs

• Clarity against frames. Recursive code often mirrors the definition of the problem and is easier to get right, but every call costs a function call and a frame, and a deep recursion holds all of its frames at once.
• Depth limits. CPython raises RecursionError when the interpreter stack reaches sys.getrecursionlimit(), 1000 by default. sys.setrecursionlimit() raises the limit, and the docs warn that setting it too high can crash Python: the limit is there so that runaway recursion stops with an exception before it overflows the process's real stack, which would end the process instead. Since 3.11 most calls from Python code to Python functions no longer use the C stack, so the limit can go much higher than it used to, and since 3.12 recursion inside built-in functions is guarded by a separate mechanism; every frame still costs memory. The JVM throws StackOverflowError, an Error rather than an Exception; the thread stack size is set with -Xss and defaults to 1024 KB on Linux and macOS for x64 and 2048 KB for AArch64, while on Windows it depends on virtual memory (java command). JavaScript engines throw RangeError: Maximum call stack size exceeded (Chrome, Safari) or InternalError: too much recursion (Firefox) (MDN).
• A missing base case fails late. Infinite recursion doesn't hang. It fills the stack and raises the same RecursionError whatever the limit, after a long traceback that Python shortens to "Previous line repeated … more times".
• Repeated work. Branching recursion over overlapping subproblems takes exponential time. Memoization fixes the time but not the depth: a cold fib_memo(5000) still raises RecursionError at the default limit, so compute large tables bottom-up.
• Tail calls are not portable. Code that counts on tail-call elimination runs in Scheme and in Safari, and overflows the stack almost everywhere else.

Implementation notes

• Python: sys.getrecursionlimit() and sys.setrecursionlimit() read and set the limit, and RecursionError (a subclass of RuntimeError, added in 3.5) is the exception to catch. threading.stack_size() sets the native stack size of threads started after the call. functools.cache and functools.lru_cache memoize, and math.factorial is the factorial to use in real code.
• Parsers and serializers cap nesting. Python's json module raises RecursionError on input nested deeper than the stack allows (try json.loads("[" * 100_000 + "]" * 100_000)), and .NET's System.Text.Json stops at a depth of 64 unless you raise JsonSerializerOptions.MaxDepth (docs).
• APIs: a GraphQL query is a tree the server resolves field by field, so the GraphQL security guidance recommends limiting how deeply an operation may nest. In a federated graph the router is the place to enforce it (GraphQL Federation).
• Databases: SQL's WITH RECURSIVE walks hierarchies such as org charts, bills of materials and graph edges. Despite the name, PostgreSQL evaluates it iteratively, re-running the recursive part on a working table until it yields no new rows (PostgreSQL docs).
• Measure the depth, not the input size. The stack grows with the deepest chain of pending calls, so a tree with a million nodes is fine if it is balanced and fails if it degenerates into a list.