Recursion: base cases and the call stack

A recursive function solves a problem by calling itself on a smaller version of the same problem. It needs two cases. The base case is an input small enough to answer directly, without another call. The recursive case makes the input smaller, calls the function on it, and builds its own answer from what that call returns. Every call gets a frame of its own on the call stack, holding its arguments and local variables until it returns, which is how one function can be in the middle of several calls at once. This lesson writes recursive functions with both cases, traces them on the call stack and as recursion trees, counts the calls and the stack depth of two well-known recursions, and turns recursion into loops and back.

The base case and the recursive case

The sum of the digits of 472 is 4 + 7 + 2 = 13. Put another way, it is the digit sum of 47, plus the last digit, 2. That second description is recursive: it answers the question for 472 with the same question about a smaller number. A number with one digit needs no further question; it is its own digit sum.

def digit_sum(n):
    """The sum of the decimal digits of a whole number n >= 0."""
    if n < 10:  # base case: a single digit is its own sum
        return n
    # recursive case: the same question about a number with one digit fewer
    return digit_sum(n // 10) + n % 10


for n in (7, 472, 9_999, 1_234_567):
    print(f"digit_sum({n}) = {digit_sum(n)}")

digit_sum(7) = 7
digit_sum(472) = 13
digit_sum(9999) = 36
digit_sum(1234567) = 28

Both cases are visible in the code. n < 10 is the base case, answered at once. Otherwise n // 10 drops the last digit, the call digit_sum(n // 10) answers the smaller question, and + n % 10 adds the digit that was dropped. NIST’s Dictionary of Algorithms and Data Structures describes every recursive solution the same way: base cases solved directly, and recursive cases that split the problem into smaller parts, call the function on each part and combine the answers.

Two checks make such a function correct, and they are the same two that the lesson on correctness used for loops.

1. It stops. Every recursive call must get closer to a base case. Here the number of digits falls by one on each call, and a count that falls by one cannot fall forever, so digit_sum always reaches a number below 10.
2. It returns the right answer. Assume the call on the smaller input returns the right answer, and check that the case you are writing then returns the right answer too. If digit_sum(47) is 11, then digit_sum(472) is 11 + 2 = 13, which is correct. The base cases are right on their own, so the argument covers every input, one digit at a time: this is proof by induction, written as code.

A base case that is never reached

The second check is easy to get right and the first is easy to miss. This countdown moves in steps of two and stops at zero:

def countdown(n):
    """Count down to zero in steps of two."""
    if n == 0:
        return "liftoff"
    return countdown(n - 2)


print(countdown(6))  # 6, 4, 2, 0: reaches the base case
try:
    print(countdown(7))  # 7, 5, 3, 1, -1, -3 ... steps over 0
except RecursionError as error:
    print("RecursionError:", error)

liftoff
RecursionError: maximum recursion depth exceeded

From 6 it reaches 0: 6, 4, 2, 0. From 7 it goes 7, 5, 3, 1, −1, −3 and never meets 0, so every call makes another call. Python does not let that go on until the program crashes. It counts the frames on its stack, and when the count reaches the recursion limit (sys.getrecursionlimit(), 1,000 by default), it raises RecursionError. The Python documentation gives the reason for the limit: it stops infinite recursion from overflowing the C stack and crashing Python. The fix is a base case that every input reaches: if n <= 0: stops both sequences, or the function can refuse odd numbers outright.

The call stack, frame by frame

When a function calls another function, the caller pauses where it is, and the new call starts with its own variables. A recursive call works in exactly the same way, even though both calls run the same code: the Python tutorial notes that every call, recursive ones included, gets a fresh local symbol table of its own. Each paused call is kept on the call stack as a frame: its arguments, its local variables and the point in its code where it will carry on. A call pushes a frame; a return pops it and hands its value to the frame below.

This version of digit_sum prints each event, indented by the number of frames waiting below it:

depth = 0  # how many calls have started and not yet returned
deepest = 0


def digit_sum(n):
    global depth, deepest
    depth += 1
    deepest = max(deepest, depth)
    pad = "  " * (depth - 1)  # one step of indentation per waiting frame
    print(f"{pad}digit_sum({n}) starts")
    if n < 10:
        result = n
        print(f"{pad}digit_sum({n}) returns {result}")
    else:
        below = digit_sum(n // 10)  # this frame waits here
        result = below + n % 10  # work done after the call returns
        print(f"{pad}digit_sum({n}) returns {below} + {n % 10} = {result}")
    depth -= 1
    return result


digit_sum(4728)
print("frames on the stack at the deepest point:", deepest)

digit_sum(4728) starts
  digit_sum(472) starts
    digit_sum(47) starts
      digit_sum(4) starts
      digit_sum(4) returns 4
    digit_sum(47) returns 4 + 7 = 11
  digit_sum(472) returns 11 + 2 = 13
digit_sum(4728) returns 13 + 8 = 21
frames on the stack at the deepest point: 4

Read it from the top. Four calls start before any returns, so four frames are on the stack at the deepest point, one per digit. Then the returns come back in the opposite order, and each frame does the work that was waiting for the call below it: 4 + 7, then 11 + 2, then 13 + 8. Nothing is added on the way down; all the additions happen on the way back up.

The stack is last in, first out, and that is the order recursion needs: the call that started last is the one that must finish first, because the calls below it are waiting for its result.

Recursion trees: how much work, how deep

A recursion tree draws every call as a node, with the calls it makes as its children (NIST lists recursion trees as a way to analyse the cost of a recursive algorithm). Two numbers can be read straight off a tree. The number of nodes is the number of calls, which sets the running time. The height, the longest path from the root to a leaf, is the largest number of frames on the stack at once, which sets the memory.

The Fibonacci numbers, written straight from their definition fib(n) = fib(n − 1) + fib(n − 2), make two calls in every call that is not a base case:

The tree for fib(5) has 15 nodes, and the same calls appear again and again: fib(3) is computed twice and fib(2) three times. Its height is only 5. Fast exponentiation is the opposite shape. To compute 3¹⁰⁰⁰, compute 3⁵⁰⁰ once and square it; for an odd exponent, multiply by 3 once more. Each call makes one call with half the exponent, so the tree is a single path. This program counts the calls and the deepest stack of both:

MOD = 10**9 + 7  # keep the powers small by working modulo a large prime
calls = 0
depth = deepest = 0


def enter():
    global calls, depth, deepest
    calls += 1
    depth += 1
    deepest = max(deepest, depth)


def leave(value):
    global depth
    depth -= 1
    return value


def fib(n):
    """The n-th Fibonacci number, straight from its definition: each call makes two."""
    enter()
    if n < 2:
        return leave(n)
    return leave(fib(n - 1) + fib(n - 2))


def power(base, exp):
    """base ** exp % MOD by halving the exponent: each call makes one."""
    enter()
    if exp == 0:
        return leave(1)
    half = power(base, exp // 2)
    result = half * half % MOD
    if exp % 2:
        result = result * base % MOD
    return leave(result)


print("fib(n): two calls per call")
print("     n       fib(n)       calls  deepest")
for n in (5, 10, 20, 25):
    calls = deepest = 0
    value = fib(n)
    print(f"{n:>6} {value:>12,} {calls:>11,} {deepest:>8}")

print("power(3, e) modulo 10**9 + 7: one call per call, e halves")
print("     e       result       calls  deepest  same as pow()")
for label, e in (("10", 10), ("1,000", 1_000), ("10**6", 10**6), ("10**18", 10**18)):
    calls = deepest = 0
    value = power(3, e)
    print(f"{label:>6} {value:>12} {calls:>11} {deepest:>8}  {value == pow(3, e, MOD)}")

fib(n): two calls per call
     n       fib(n)       calls  deepest
     5            5          15        5
    10           55         177       10
    20        6,765      21,891       20
    25       75,025     242,785       25
power(3, e) modulo 10**9 + 7: one call per call, e halves
     e       result       calls  deepest  same as pow()
    10        59049           5        5  True
 1,000     56888193          11       11  True
 10**6     64935414          21       21  True
10**18    246336683          61       61  True

The two recursions are far apart. fib(25) makes 242,785 calls, yet never has more than 25 frames on the stack: the time explodes while the memory stays small. In general fib(n) makes 2 · fib(n + 1) − 1 calls; for n = 25 that is 2 × 121,393 − 1. Fast power reaches an exponent of 10¹⁸ in 61 calls, one for each of its 60 binary digits plus one for the exponent 0, and its result matches Python’s built-in pow(3, e, MOD). Working modulo 10⁹ + 7 keeps every number small; the full value of 3 to the power 10¹⁸ would have about 4.8 × 10¹⁷ digits. A tree that branches needs care with time; a tree that is one long path needs care with depth.

Work after the call keeps the frame alive

In digit_sum, the addition happens after the recursive call returns, so each frame has to stay on the stack until then. The same is true of this way of reversing a text, which reverses everything after the first character and then appends that character:

def reverse(text):
    """Work after the call: each frame waits to add its first character."""
    if text == "":
        return ""
    return reverse(text[1:]) + text[0]


def reverse_acc(text, done=""):
    """A tail call: the recursive call is the last thing the function does."""
    if text == "":
        return done
    return reverse_acc(text[1:], text[0] + done)


print(reverse("recursion"), reverse_acc("recursion"))

long_text = "ab" * 2_500  # 5,000 characters: one call per character
for f in (reverse, reverse_acc):
    try:
        f(long_text)
        print(f.__name__, "reversed 5,000 characters")
    except RecursionError:
        print(f.__name__, "raised RecursionError on 5,000 characters")

noisrucer noisrucer
reverse raised RecursionError on 5,000 characters
reverse_acc raised RecursionError on 5,000 characters

reverse_acc passes the part already reversed along as an argument, so its recursive call is the last thing it does. That is a tail call. NIST describes how a compiler may optimise tail recursion away, running the call in the current frame instead of creating a new one. CPython does not: the notes for Python 3.14 say that tail call optimisation of Python functions is not implemented. The run shows the consequence, since both versions fail on a text of 5,000 characters, one frame per character, well past the limit of 1,000. Both are also slower than they look, because text[1:] copies the rest of the text on every call, which makes them take time proportional to n² for a text of n characters. In Python, a recursion whose depth grows with the size of its input is a bug waiting for a large input.

From recursion to a loop, and back

A recursion that makes one call per call, with the call as its last step or followed only by a little work, turns into a loop by a fixed recipe:

• the base-case test becomes the loop’s exit condition;
• the smaller argument becomes the next value of the loop variable;
• the work done after each call is done in the loop instead, into a variable that collects the answer.

The reverse direction works too. A loop over a sequence becomes a recursion on a shorter sequence: the base case is the empty sequence, and the recursive case handles the first item and recurses on the rest.

import random


def digit_sum_rec(n):
    if n < 10:
        return n
    return digit_sum_rec(n // 10) + n % 10


def digit_sum_loop(n):
    total = 0
    while n >= 10:  # the recursive case becomes the loop condition
        total += n % 10  # the work done after each call, done now instead
        n //= 10  # the smaller argument becomes the new value of n
    return total + n  # the base case ends the loop


def count_vowels_loop(text):
    count = 0
    for ch in text:
        if ch in "aeiou":
            count += 1
    return count


def count_vowels_rec(text):
    if text == "":  # an empty text has no vowels
        return 0
    first = 1 if text[0] in "aeiou" else 0
    return first + count_vowels_rec(text[1:])  # the rest of the text is smaller


rng = random.Random(7)
numbers = [rng.randrange(10**12) for _ in range(10_000)]
words = ["".join(rng.choice("abcdeiou") for _ in range(rng.randrange(60))) for _ in range(10_000)]
print("digit sums agree:", all(digit_sum_rec(n) == digit_sum_loop(n) for n in numbers))
print("vowel counts agree:", all(count_vowels_rec(w) == count_vowels_loop(w) for w in words))
print("digit_sum_loop(472) =", digit_sum_loop(472), " count_vowels_rec('recursion') =", count_vowels_rec("recursion"))

digit sums agree: True
vowel counts agree: True
digit_sum_loop(472) = 13  count_vowels_rec('recursion') = 4

The loop version of digit_sum keeps one running total instead of one frame per digit, so its extra memory no longer grows with the input. count_vowels_rec shows the other direction; it is easy to read, and it fails on a text of a few thousand characters for the reasons above, which is why Python code scans sequences with loops. Comparing the two versions on thousands of random inputs is a cheap test that the conversion changed nothing.

Recursions that branch, such as fib or a walk through a tree, do not reduce to one running variable: the pending calls themselves are the state. They convert to a loop with an explicit stack, a list that holds the work still to do, which the next lesson builds.

When recursion is the right tool

The CS2023 curriculum asks students to explain the benefits and drawbacks of an iterative and a recursive solution to the same problem, and the two differ in a few predictable ways:

Recursion is the natural tool when the data contains smaller copies of itself: a list of lists, a folder of folders, a tree whose children are trees. It is also the shape of divide and conquer, such as merge sort and binary search, and of the searches in the rest of this module, which try one choice, recurse, and try the next. A plain scan of a list, or a count up to n, is clearer as a loop, and in Python it is the only choice that works for large n.

Exercise

def flatten(nested):
    """Every integer of a nested list, in order, as one new flat list."""
    # This flattens one level only. Make it work at any depth.
    out = []
    for item in nested:
        if isinstance(item, list):
            out.extend(item)
        else:
            out.append(item)
    return out

import copy

from flatten import flatten


def test_flat_list():
    """a list without inner lists comes back unchanged"""
    assert flatten([4, 8, 15]) == [4, 8, 15]


def test_mixed_depths():
    """integers at several depths come out in order"""
    assert flatten([1, [2, [3, 4]], 5]) == [1, 2, 3, 4, 5]
    assert flatten([[[[9]]], 8, [7, [6]]]) == [9, 8, 7, 6]


def test_empty_lists():
    """empty lists, at any depth, contribute nothing"""
    assert flatten([]) == []
    assert flatten([[], [[]], [[], [7]]]) == [7]


def test_order_is_kept():
    """the integers keep the order in which they appear"""
    assert flatten([[3, [1]], 2, [[5], 4]]) == [3, 1, 2, 5, 4]


def test_two_hundred_levels():
    """a list nested 200 levels deep"""
    nested = [200]
    for value in range(199, 0, -1):
        nested = [value, nested]
    assert flatten(nested) == list(range(1, 201))


def test_input_left_alone():
    """flatten builds a new list and leaves its input as it was"""
    data = [1, [2, [3]], [], 4]
    before = copy.deepcopy(data)
    result = flatten(data)
    assert data == before
    assert result is not data

Interview questions

Fresher · What do the base case and the recursive case of a recursive function do, and what happens when the base case is never reached?

The base case answers the smallest inputs directly, without another call, and it is what finally stops the recursion. The recursive case reduces the input, calls the same function on the smaller input and builds its own answer from that result, as digit_sum(472) adds 2 to digit_sum(47). Every recursive call must move closer to a base case, by a measure that cannot shrink forever, such as the number of digits or the length of a list. When some input never reaches a base case, as a countdown in steps of two does from an odd number, each call makes another call and every frame stays on the stack. Python stops at its recursion limit, 1,000 frames by default, with RecursionError; other languages stop when the thread’s stack runs out, with an error such as Java’s StackOverflowError or, in C and C++, a crash.

Key takeaways

• A recursive function has base cases, answered directly, and recursive cases that call it on a smaller input and combine the result.
• It is correct if every call gets closer to a base case and each case is right whenever the smaller calls are: proof by induction.
• Each call has its own frame on the call stack; returns come back in the opposite order of the calls, and work after a call happens on the way back up.
• A recursion tree shows the cost: its nodes are the calls (time), its height is the stack depth (memory). fib(25) makes 242,785 calls at depth 25; fast power reaches 10¹⁸ in 61 calls.
• CPython keeps a frame for every call, tail calls included, and stops at 1,000 frames by default; scan sequences with loops and keep recursion for nested and branching problems.