Recursion & Recursive Data

The most important conceptual distinction in this module is between the procedure (the code you write) and the process (the computation that unfolds at runtime).

A recursive procedure is one that calls itself syntactically. But a recursive procedure can generate either a recursive process (one that builds up a chain of deferred operations, requiring stack space proportional to the depth) or an iterative process (one that stays flat, using only constant auxiliary space beyond the accumulator).

Consider computing factorial:

# Recursive process: builds deferred multiplications
def fact_rec(n):
    if n == 0:
        return 1
    return n * fact_rec(n - 1)  # must remember 'n *' for each call

The call fact_rec(4) expands like:

fact_rec(4)
4 * fact_rec(3)
4 * (3 * fact_rec(2))
4 * (3 * (2 * fact_rec(1)))
4 * (3 * (2 * (1 * fact_rec(0))))
4 * (3 * (2 * (1 * 1)))
...
24

Notice the growing triangle of pending work. Now consider:

# Iterative process (via tail-recursive procedure)
def fact_iter(n, acc=1):
    if n == 0:
        return acc
    return fact_iter(n - 1, acc * n)  # no deferred work: acc carries state

The call fact_iter(4) stays flat:

fact_iter(4, 1)
fact_iter(3, 4)
fact_iter(2, 12)
fact_iter(1, 24)
fact_iter(0, 24)
24

Both are recursive procedures, but they generate fundamentally different processes. SICP calls this one of the key lessons: "syntactic sugar" does not change the underlying process shape. An iterative process can be described by a recursive procedure — the structure of the process is determined by when the recursive call returns value versus when it defers work.

def fact_rec(n):
    if n == 0:
        return 1
    return n * fact_rec(n - 1)   # deferred: 'n *' must be remembered

def fact_iter(n, acc=1):
    if n == 0:
        return acc
    return fact_iter(n - 1, acc * n)  # no deferred work

To understand why a recursive process uses O(n) stack space, you need a mental model of how function calls work. The substitution model (from SICP) is the simplest: to evaluate f(x), substitute x into the body of f and evaluate the result. Each unevaluated expression is 'deferred' until its operands are ready.

At the hardware level, each function call pushes an activation record (stack frame) onto the call stack. The frame contains the local variables, the return address, and the arguments. When a function returns, its frame is popped. For a deeply recursive call like fact_rec(10000), you push 10000 frames before you pop any — this can overflow the stack (Python's default limit is ~1000 frames; C's stack is typically 1–8 MB).

An iterative process, by contrast, only needs one frame at a time (assuming the language implements tail-call optimization — more on this below). The current frame is reused rather than stacked.

The key insight: deferred operations are debt. Each n * fact_rec(n-1) is a note saying "I still owe a multiplication after the recursive call finishes." That note must be stored somewhere — and the call stack is where the hardware stores it. Eliminating all deferred operations eliminates the debt, and the call stack stays flat.

This is also why stack overflows happen on recursive algorithms over large inputs, and why understanding this model lets you reason about memory usage precisely.

# Trace the stack depth for fact_rec(4):
# Frame 4: n=4, waiting for fact_rec(3)
#   Frame 3: n=3, waiting for fact_rec(2)
#     Frame 2: n=2, waiting for fact_rec(1)
#       Frame 1: n=1, waiting for fact_rec(0)
#         Frame 0: n=0, returns 1  <-- deepest
#       Frame 1 resumes: returns 1*1 = 1
#     Frame 2 resumes: returns 2*1 = 2
#   Frame 3 resumes: returns 3*2 = 6
# Frame 4 resumes: returns 4*6 = 24

Linear recursion makes at most one recursive call per activation. Tree recursion makes two or more, causing the call graph to branch into a tree.

The canonical example is the Fibonacci sequence:

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

The call tree for fib(5) has 15 calls (and fib(n) requires O(φ^n) calls where φ = 1.618...). This is exponential, despite the code looking innocent.

Why? Because fib(3) is computed twice, fib(2) three times, fib(1) five times. The tree recursion is doing redundant work on an exponential scale.

Yet tree recursion is not inherently bad. For problems where subproblems truly do not overlap, it is the right approach:

• Generating all permutations of a list: each branch explores one choice for the first element, then recurses on the rest.
• Traversing a binary tree: naturally calls left and right subtrees.
• Counting the number of ways to make change for a given amount.

The cure for overlapping subproblems is memoization: cache the result of each distinct call. This converts fib(n) from O(2^n) to O(n) — the bridge to dynamic programming.

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1:
        return n
    return fib_memo(n-1) + fib_memo(n-2)  # O(n) time, O(n) space

The fundamental lesson: tree recursion is structurally natural for tree-shaped problems, but you must recognize when subproblems overlap and add memoization.

# Naive: O(phi^n) time
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

# Memoized: O(n) time
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1:
        return n
    return fib_memo(n-1) + fib_memo(n-2)

The deepest reason recursion matters in CS is that data itself is naturally recursive. A linked list is either:

• Empty (nil), or
• A node holding a value and a pointer to another linked list.

A binary tree is either:

• A leaf (empty), or
• A node holding a value, a left binary tree, and a right binary tree.

This recursive definition is not just mathematical notation — it directly prescribes how to write functions over these structures. The base case of the recursion corresponds to the base case of the data definition; the recursive case corresponds to the recursive case of the data definition. This principle is called structural recursion or structural induction.

class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

def length(node):           # mirrors the data definition exactly
    if node is None:        # base: empty list
        return 0
    return 1 + length(node.next)  # recursive: rest is a list

def sum_tree(node):
    if node is None:        # base: empty tree
        return 0
    return node.val + sum_tree(node.left) + sum_tree(node.right)

In functional languages like Haskell, this is made completely explicit with algebraic data types:

data List a = Nil | Cons a (List a)

length :: List a -> Int
length Nil         = 0
length (Cons _ xs) = 1 + length xs

The code and the type definition are structurally isomorphic — the recursion in the code mirrors the recursion in the type. Once you see this, writing correct recursive functions becomes almost mechanical: decompose the data, handle each case, trust the recursion on sub-data.

# Binary tree in Python
class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))

def inorder(node):
    if node is None:
        return []
    return inorder(node.left) + [node.val] + inorder(node.right)

Two (or more) functions can be mutually recursive: A calls B, and B calls A. This is not a curiosity — it arises naturally in parsing and in some elegant state-machine encodings.

A clean example: testing whether a non-negative integer is even or odd without the % operator.

def is_even(n):
    if n == 0:
        return True
    return is_odd(n - 1)

def is_odd(n):
    if n == 0:
        return False
    return is_even(n - 1)

This is simultaneously silly (there is a better way) and profound: it shows that mutual recursion is equivalent to a finite state machine. is_even is the "in-even-state" function; is_odd is the "in-odd-state" function. They ping-pong between states, decrementing n at each step.

In compiler design, mutually recursive functions arise in recursive-descent parsers. A grammar rule like expression ::= term ('+' term)* leads to mutually recursive parse_expression and parse_term functions.

Mathematically, mutual recursion is covered by fixed-point theorems: the pair (is_even, is_odd) is the unique pair of functions satisfying both definitions simultaneously.

def is_even(n):
    if n == 0: return True
    return is_odd(n - 1)

def is_odd(n):
    if n == 0: return False
    return is_even(n - 1)

# Each function encodes one state of a two-state FSM

A tail call is a function call that is the very last action of a function — the caller has nothing to do after the callee returns except return that same value. In fact_iter, the last action is return fact_iter(n-1, acc*n) — a tail call.

Why does this matter? Because when a call is in tail position, the caller's stack frame is no longer needed. The callee can reuse the caller's frame rather than allocating a new one. This is tail-call optimization (TCO), and when a language implements it, tail-recursive functions run in O(1) stack space — they are equivalent to loops.

Scheme and Haskell guarantee TCO by specification. JavaScript (ES6+) mandates it in strict mode. Python famously does NOT implement TCO (Guido van Rossum deliberately omitted it); C/C++ compilers often apply it as an optimization but do not guarantee it.

How to convert a recursive process to a tail-recursive one: introduce an accumulator argument that carries the "state" that would otherwise be deferred on the stack.

; Scheme: guaranteed TCO
(define (fact-iter n acc)
  (if (= n 0)
      acc
      (fact-iter (- n 1) (* n acc))))  ; tail call

(fact-iter 1000000 1)  ; runs in O(1) space in Scheme

The key test: is the recursive call in tail position? If after the call you still need to do work (like multiply by n), it is NOT in tail position. If the call result is returned directly, it IS in tail position.

Even without TCO in the language, understanding tail calls is valuable: it tells you exactly when you can safely replace recursion with a loop, and it underpins continuation-passing style (CPS), trampolining, and other advanced techniques.

; Scheme (TCO guaranteed by standard)
(define (sum-iter lst acc)
  (if (null? lst)
      acc
      (sum-iter (cdr lst) (+ acc (car lst)))))  ; tail call

; Equivalent C with a loop (same process shape)
int sum_iter(int* arr, int n, int acc) {
    if (n == 0) return acc;
    return sum_iter(arr + 1, n - 1, acc + arr[0]);  // tail call
    // gcc -O2 will optimize this to a loop
}

A fundamental theorem of computation: recursion and iteration are equally expressive. Any function computable iteratively is computable recursively, and vice versa. This is a consequence of Church's thesis — both are Turing-complete.

Yet in practice, the choice matters:

When recursion is clearer:

• The problem is naturally tree-structured (tree traversal, parsing, divide-and-conquer).
• The algorithm mirrors the data definition (structural recursion).
• The base cases and recursive cases correspond directly to the problem's mathematical definition.

When iteration is clearer (or necessary):

• The problem is inherently sequential (reading a file line by line).
• The language lacks TCO and the depth is large (Python over large lists).
• Performance is critical and you want to avoid function-call overhead.

Converting recursion to iteration mechanically: any recursive function can be made iterative by maintaining an explicit stack (mimicking the call stack in user space). This is exactly what iterative DFS does vs. recursive DFS:

# Recursive DFS
def dfs_rec(node, visited):
    visited.add(node)
    for neighbor in node.neighbors:
        if neighbor not in visited:
            dfs_rec(neighbor, visited)

# Iterative DFS (explicit stack)
def dfs_iter(start):
    visited, stack = set(), [start]
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            stack.extend(node.neighbors)

The iterative version uses an explicit stack; the recursive version uses the call stack. They are doing the same thing — the call stack is just hidden.

The deep lesson: iteration is recursion with a fixed call depth of 1 (you only ever call the current frame again, not a new frame). Tail recursion makes this precise.

# Recursive DFS (natural, mirrors graph structure)
def dfs_rec(node, visited=None):
    if visited is None: visited = set()
    visited.add(node)
    for nb in node.neighbors:
        if nb not in visited:
            dfs_rec(nb, visited)
    return visited

# Iterative DFS (explicit stack = manual call stack)
def dfs_iter(start):
    visited, stack = set(), [start]
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            stack.extend(node.neighbors)
    return visited

Recursion and mathematical induction are two faces of the same coin. Proving a recursive function correct follows exactly the same structure as a proof by induction:

1. Base case: Verify the function is correct on the base case(s) (e.g., n=0).
2. Inductive step: Assume the function is correct for smaller inputs (the inductive hypothesis). Prove it is correct for the current input given that assumption.

This is not a metaphor — it is the formal verification method. Example: prove length(lst) returns the number of nodes.

• Base case: lst is None. length(None) = 0. A null list has 0 nodes. Correct.
• Inductive step: Assume length(lst.next) correctly returns the number of nodes in lst.next. Then length(lst) = 1 + length(lst.next) = 1 + (number of nodes in lst.next) = number of nodes in lst. Correct.

The trust you place in the recursive call is exactly the inductive hypothesis. When you write return 1 + length(node.next), you are saying "I trust, by induction, that length(node.next) is correct." Your only job is to make the current step correct given that trust.

This is why structural recursion over well-founded data structures always terminates: each recursive call is on strictly smaller data (shorter list, smaller tree), so by well-founded induction, the recursion must bottom out at the base case.

Learning to reason this way — trusting the recursive call as an inductive hypothesis, proving only the current step — is the core skill of writing correct recursive code.

# Correctness proof sketch for sum of a list:
def sum_list(lst):
    if not lst:       # base case: empty list
        return 0      # sum of empty list is 0. Correct.
    # IH: sum_list(lst[1:]) == sum of lst[1:]
    return lst[0] + sum_list(lst[1:])
    # Therefore: lst[0] + sum(lst[1:]) == sum(lst). Correct.

A beautiful non-trivial example of tree recursion is the counting change problem from SICP: given n cents and a list of coin denominations, how many distinct ways can you make change?

The key insight is a purely recursive decomposition:

• Ways to make change for n using coins [c, ...] = (ways using at least one c) + (ways using no c at all).
• The first term recurses on n - c with the same coin list (we used one c).
• The second term recurses on n with the rest of the coins (we skip c forever).

def count_change(n, coins=(50, 25, 10, 5, 1)):
    if n == 0:
        return 1           # exactly one way: use no more coins
    if n < 0 or not coins:
        return 0           # impossible
    return (count_change(n - coins[0], coins) +  # use first coin at least once
            count_change(n, coins[1:]))           # never use first coin

This is elegant but exponential. The recursive call tree branches at every step. For count_change(100), there are overlapping subproblems: count_change(50, (10,5,1)) is computed many times.

Adding memoization (or converting to bottom-up DP) makes it polynomial. The counting-change problem is one of the most instructive examples because:

1. The tree recursion falls out naturally from a purely logical decomposition.
2. The exponential blowup is obvious once you draw the tree.
3. Memoization is the surgical fix — the logical structure remains intact.

This is the template for recognizing DP problems: if a tree-recursive solution has overlapping subproblems, memoize it.

from functools import lru_cache

@lru_cache(maxsize=None)
def count_change(n, coins=(50, 25, 10, 5, 1)):
    if n == 0: return 1
    if n < 0 or not coins: return 0
    return (count_change(n - coins[0], coins) +
            count_change(n, coins[1:]))

print(count_change(100))  # 292

One of the most important applications of recursive data structures is the abstract syntax tree (AST) — the data structure that compilers and interpreters use to represent programs.

An arithmetic expression like (3 + 4) * (2 - 1) is naturally a tree:

       *
      / \
     +   -
    / \ / \
   3  4 2  1

Evaluating it follows the recursive structure exactly:

class Num:
    def __init__(self, val): self.val = val

class BinOp:
    def __init__(self, op, left, right):
        self.op, self.left, self.right = op, left, right

def evaluate(expr):
    if isinstance(expr, Num):
        return expr.val                              # base case
    left  = evaluate(expr.left)                     # recurse
    right = evaluate(expr.right)                    # recurse
    if expr.op == '+': return left + right
    if expr.op == '*': return left * right
    if expr.op == '-': return left - right

This pattern — interpreter / evaluator over a recursive data type — is the skeleton of every programming language implementation. Scheme interpreters are often under 100 lines because the language's structure is so cleanly recursive. Pattern matching in functional languages (Haskell, OCaml, Rust) makes this correspondence even more explicit: each case of the evaluate function corresponds directly to one constructor of the AST type.

Building and evaluating expression trees is the prototype for understanding how computers run programs.

class Num:
    def __init__(self, val): self.val = val

class BinOp:
    def __init__(self, op, left, right):
        self.op, self.left, self.right = op, left, right

def evaluate(expr):
    if isinstance(expr, Num):
        return expr.val
    l = evaluate(expr.left)
    r = evaluate(expr.right)
    ops = {'+': l+r, '-': l-r, '*': l*r, '/': l/r}
    return ops[expr.op]

# (3 + 4) * (2 - 1)
tree = BinOp('*', BinOp('+', Num(3), Num(4)), BinOp('-', Num(2), Num(1)))
print(evaluate(tree))  # 7