Recursion

A recursive function is one that solves a problem by calling itself on a smaller version of the same problem. Recursion is the natural way to work with structures that are defined in terms of themselves, and many of the structures in the rest of this course are: a binary tree is a node with two smaller binary trees beneath it, a directory is a list of files and smaller directories, and a well-formed expression contains smaller expressions inside parentheses. Recursion is also how divide-and-conquer algorithms such as binary search, merge sort and quicksort are most clearly written. This lesson explains how recursion works on a real machine, how to reason about its correctness and cost, and when an engineer should replace it with a loop.

Jonah meets recursion on the server first. Northway stores its configuration files in a directory tree: one folder per city, a folder per corridor inside each city, and a file per node, with occasional subfolders for archived settings. Maren asks him for a function that counts every node configuration file under a given folder, however deeply nested. A loop over a single folder is easy; a loop over folders of unknown depth is not. Recursion makes it easy again: the count for a folder is the number of files directly in it plus the count for each of its subfolders.

Base case and recursive case

Every correct recursive function has two parts. The base case handles the smallest inputs directly, without recursion: an empty list, a folder with no subfolders, n = 0. The recursive case reduces the problem to one or more smaller instances, calls itself on them, and combines the results. Two conditions guarantee that the recursion ends: every recursive call must be on an input that is strictly smaller by some measure, and every chain of smaller inputs must eventually reach a base case. Forgetting the base case, or making a recursive call on an input that is not smaller, gives infinite recursion, which on a real machine ends when the call stack runs out of space.

# Recursive count of node configuration files in a nested folder tree
tree = {
    "kingston": {
        "princess-st": {"ns4-0101.cfg": None, "ns4-0102.cfg": None},
        "hwy-401": {"ns4-0201.cfg": None, "ns4-0202.cfg": None, "ns4-0203.cfg": None,
                    "archive": {"ns4-0201-2024.cfg": None}},
    },
    "readme.txt": None,
}

def count_cfg(folder, depth=0):
    total = 0
    for name, sub in folder.items():
        if sub is None:                        # a file: base case
            total += name.endswith(".cfg")
        else:                                  # a folder: recursive case on a smaller tree
            n = count_cfg(sub, depth + 1)
            print("  " * depth + f"{name}/: {n}")
            total += n
    return total

print("total:", count_cfg(tree))

  princess-st/: 2
    archive/: 1
  hwy-401/: 4
kingston/: 6
total: 6

Reading the output from the bottom up shows the order in which the calls finish: the deepest folders report first, and each folder's total includes its children's totals. The function never needed to know how deep the tree was. That is the essence of recursive thinking: trust that the recursive call correctly solves the smaller problem, and concentrate only on how to combine the results and on the base case. This trust is not blind; it is mathematical induction. If the base case is right, and if the function is right for an input whenever it is right for all smaller inputs, then it is right for every input.

What happens on the call stack

Lesson 5 described the processor's call stack. Each call to a function, recursive or not, pushes a frame holding the return address, saved registers, the arguments and the local variables. A recursive call is just another call, so it pushes another frame on top, with its own copies of the arguments and locals. When the base case returns, its frame is popped and control goes back to the caller's frame, which still holds that caller's own local values. The depth of recursion therefore costs memory: a recursion d levels deep keeps d frames on the stack at once.

Stack depth is the main practical danger of recursion. Python limits recursion depth to about 1,000 frames by default and raises RecursionError beyond it, which protects the interpreter but means a recursive function over a 10,000-node linked list will fail. In C there is no such check: the stack simply grows into whatever memory lies beyond it. On the NS-4, with a 4 KB main-loop stack, a recursive routine that uses 48 bytes per frame can go only about 80 levels deep before it corrupts memory, minus whatever the rest of the call chain is already using. That is why many embedded coding standards, including the widely used MISRA C guidelines, forbid recursion outright in safety-related code: its stack use depends on the data, and a worst-case bound is hard to prove.

Analysing recursive algorithms with recurrences

The cost of a recursive algorithm is described by a recurrence, an equation that expresses the cost on an input of size n in terms of the cost on smaller inputs. Factorial does a constant amount of work and then one recursive call on n − 1, so T(n) = T(n − 1) + c, which unrolls to T(n) = c·n + T(0), which is O(n). Binary search does constant work and one recursive call on half the range: T(n) = T(n/2) + c. Unrolling gives c added once for each halving, log₂ n times, so T(n) is O(log n). Merge sort, covered in lesson 11, makes two recursive calls on halves and does linear work to combine them: T(n) = 2T(n/2) + c·n, which solves to O(n log n).

A recurrence also warns you when recursion is a bad idea. The direct recursive definition of the Fibonacci numbers, fib(n) = fib(n − 1) + fib(n − 2), makes two calls for each call, and the calls overlap: fib(n − 2) is computed once directly and again inside fib(n − 1). The recurrence T(n) = T(n − 1) + T(n − 2) + c grows like the Fibonacci numbers themselves, about 1.6ⁿ, which is exponential. Computing fib(40) this way takes over 300 million calls. Remembering each result the first time it is computed, a technique called memoization, cuts that to 41 calls, and a simple loop that keeps the last two values does the same with no recursion at all.

# Counting calls: naive recursion, memoized recursion and a loop
from functools import lru_cache

calls = 0
def fib_naive(n):
    global calls
    calls += 1
    return n if n < 2 else fib_naive(n - 1) + fib_naive(n - 2)

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

def fib_loop(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

for n in (10, 20, 25):
    calls = 0
    v = fib_naive(n)
    print(f"fib({n}) = {v}: naive recursion made {calls:,} calls")
print("fib(90) memoized:", fib_memo(90), "| loop:", fib_loop(90),
      "| memo cache entries:", fib_memo.cache_info().currsize)

fib(10) = 55: naive recursion made 177 calls
fib(20) = 6765: naive recursion made 21,891 calls
fib(25) = 75025: naive recursion made 242,785 calls
fib(90) memoized: 2880067194370816120 | loop: 2880067194370816120 | memo cache entries: 91

Tail recursion and converting recursion to loops

A recursive call is a tail call when it is the very last thing the function does, with nothing left to compute after it returns. A tail-recursive function can be turned mechanically into a loop: replace the call with updating the parameters and jumping back to the start. Some languages and compilers do this automatically, a feature called tail-call optimization, so tail recursion uses constant stack space. C compilers often do it at higher optimization levels, but the C standard does not require it, so embedded code cannot rely on it. Python never does it, by design. In either language, when depth could be large, the safe course is to write the loop yourself.

Recursion that is not tail recursion, such as walking a tree with two children per node, can still be converted to a loop by managing an explicit stack data structure instead of the call stack. Push the starting item; then, while the stack is not empty, pop an item, process it and push its children. The explicit stack lives in a data structure you control: on a server it can grow on the heap far beyond the call stack's limits, and on a microcontroller it can be a fixed array whose maximum size you set and check. The order of processing differs slightly from the recursive version unless you push children in reverse, but the set of items visited is the same.

/* Iterative depth-first walk of a configuration tree with an explicit, bounded stack */
#include <stddef.h>

typedef struct cfgnode {
    const char *name;
    struct cfgnode *child, *sibling;      /* first child and next sibling */
    int is_file;
} cfgnode_t;

#define WALK_MAX 64                         /* hard limit, checked below */

int count_files(const cfgnode_t *root)
{
    const cfgnode_t *stack[WALK_MAX];
    int top = 0, files = 0;
    stack[top++] = root;
    while (top > 0) {
        const cfgnode_t *n = stack[--top];
        if (n->is_file) { files++; continue; }
        for (const cfgnode_t *c = n->child; c != NULL; c = c->sibling) {
            if (top == WALK_MAX) return -1;   /* too deep or too wide: report, don't overflow */
            stack[top++] = c;
        }
    }
    return files;
}

The C version shows what an embedded reviewer wants to see: a hard limit on the stack, a check before every push, and a defined result, here −1, when the limit is exceeded. Its worst-case memory use is exactly 64 pointers, 256 bytes on the NS-4, regardless of the input. The recursive version would have been shorter, but its stack use would have depended on the shape of the tree, and the first sign of trouble would have been a corrupted variable somewhere else in the program.

When recursion is the right choice

None of this means recursion should be avoided. On a server, for problems whose depth is naturally small, recursion is often the clearest and least error-prone code. A balanced binary tree with a billion nodes is only about 30 levels deep, so recursive tree algorithms are entirely safe there. Divide-and-conquer algorithms such as merge sort recurse only about log₂ n levels. Parsers for nested input recurse as deep as the nesting, which is small for real input, provided you also guard against deliberately malicious input with a depth limit. The engineering rule is to know the maximum depth, compare it with the stack available, and switch to an explicit stack or a loop when the depth depends on unbounded data, such as the length of a list.