Recursion

A function that solves a problem by calling itself on a smaller version of the same problem, until the problem is so small the answer is obvious.

Ingredients	Cost to watch	Typical tools
a base case and a smaller recursive case	call-stack depth and repeated work	recurrences, the master theorem, memoization

The idea

To move a tower of 3 discs in the Tower of Hanoi puzzle, you do not need to plan 7 moves. You only need to see this: if you could move the top 2 discs out of the way, you would move the big disc, then move the 2 discs back on top of it. Moving 2 discs is the same puzzle, smaller. And moving 0 discs is nothing at all.

That is recursion. Every recursive function has:

1. A base case that is answered directly (0 discs: do nothing; \(0! = 1\)).
2. A recursive case that reduces the problem to smaller versions of itself and combines their answers.

You trust the recursive call to work on the smaller problem, the same way a proof by induction trusts the step before. If every call makes the problem smaller and the base case is right, the function is right.

Each call waits for the calls it makes, so the computer keeps a call stack of unfinished calls. Its depth is the extra memory recursion uses; if it gets too deep (around a thousand frames in Python by default, more in Java and C++), the program crashes with a stack overflow.

How it works: the Tower of Hanoi

Move \(n\) discs from peg A to peg C using peg B, one disc at a time, never a larger disc on a smaller one:

1. If \(n = 0\), stop.
2. Move \(n-1\) discs from A to B (using C).
3. Move disc \(n\) from A to C.
4. Move \(n-1\) discs from B to C (using A).

Code

PythonJavaC++

def hanoi(n, source, target, spare, moves):
    """Moves n discs from source to target, never putting a disc on a smaller one."""
    if n == 0:                               # base case: nothing to move
        return
    hanoi(n - 1, source, spare, target, moves)   # 1. move the n-1 smaller discs out of the way
    moves.append((n, source, target))            # 2. move the biggest disc
    hanoi(n - 1, spare, target, source, moves)   # 3. move the n-1 smaller discs on top of it


def factorial(n):
    """n! = n * (n-1)!, with 0! = 1."""
    return 1 if n == 0 else n * factorial(n - 1)


if __name__ == "__main__":
    moves = []
    hanoi(3, "A", "C", "B", moves)
    for disc, a, b in moves:
        print(f"disc {disc}: {a} -> {b}")
    for n in [1, 2, 3, 10, 20]:
        m = []
        hanoi(n, "A", "C", "B", m)
        print(f"{n} discs: {len(m)} moves")
    print(factorial(10))

import java.util.ArrayList;
import java.util.List;

public class Hanoi {
    record Move(int disc, char from, char to) {}

    /** Moves n discs from source to target, never putting a disc on a smaller one. */
    static void hanoi(int n, char source, char target, char spare, List<Move> moves) {
        if (n == 0) return;                           // base case: nothing to move
        hanoi(n - 1, source, spare, target, moves);   // 1. move the n-1 smaller discs out of the way
        moves.add(new Move(n, source, target));       // 2. move the biggest disc
        hanoi(n - 1, spare, target, source, moves);   // 3. move the n-1 smaller discs on top of it
    }

    /** n! = n * (n-1)!, with 0! = 1. */
    static long factorial(int n) { return n == 0 ? 1 : n * factorial(n - 1); }

    public static void main(String[] args) {
        List<Move> moves = new ArrayList<>();
        hanoi(3, 'A', 'C', 'B', moves);
        for (Move m : moves) System.out.println("disc " + m.disc() + ": " + m.from() + " -> " + m.to());
        for (int n : new int[]{1, 2, 3, 10, 20}) {
            List<Move> m = new ArrayList<>();
            hanoi(n, 'A', 'C', 'B', m);
            System.out.println(n + " discs: " + m.size() + " moves");
        }
        System.out.println(factorial(10));
    }
}

#include <iostream>
#include <tuple>
#include <vector>
using namespace std;

using Move = tuple<int, char, char>;

// Moves n discs from source to target, never putting a disc on a smaller one.
void hanoi(int n, char source, char target, char spare, vector<Move>& moves) {
    if (n == 0) return;                              // base case: nothing to move
    hanoi(n - 1, source, spare, target, moves);      // 1. move the n-1 smaller discs out of the way
    moves.emplace_back(n, source, target);           // 2. move the biggest disc
    hanoi(n - 1, spare, target, source, moves);      // 3. move the n-1 smaller discs on top of it
}

// n! = n * (n-1)!, with 0! = 1.
long long factorial(int n) { return n == 0 ? 1 : n * factorial(n - 1); }

int main() {
    vector<Move> moves;
    hanoi(3, 'A', 'C', 'B', moves);
    for (auto& [disc, a, b] : moves) cout << "disc " << disc << ": " << a << " -> " << b << "\n";
    for (int n : {1, 2, 3, 10, 20}) {
        vector<Move> m;
        hanoi(n, 'A', 'C', 'B', m);
        cout << n << " discs: " << m.size() << " moves\n";
    }
    cout << factorial(10) << "\n";
}

The programs print the 7 moves for 3 discs, then the move counts 1, 3, 7, 1023 and 1048575, and \(10! = 3628800\).

When to use it

• The problem splits into smaller copies of itself: trees, nested data, divide and conquer (merge sort, quicksort), depth-first search, backtracking.
• The recursive version is much clearer than the loop version.
• Prefer a loop when the recursion is just a straight line (like factorial) and could be very deep, or in Python for depths beyond about a thousand.

Common mistakes

• No base case, or one that is never reached (for example, the argument does not shrink): infinite recursion and a stack overflow.
• Repeating work. Naive recursive Fibonacci recomputes the same values exponentially often. Remembering answers (memoization) fixes it: see dynamic programming.
• Too deep for the stack: recursion on a linked list or a path of \(10^6\) nodes needs a loop or an explicit stack.
• Modifying shared state without undoing it, in backtracking.

Going deeper

Each part below starts closed; open the ones you want.

Sample walkthrough: the calls of hanoi(3, A, C, B)

Indentation shows depth in the call stack.

hanoi(3, A→C)
  hanoi(2, A→B)
    hanoi(1, A→C)      move disc 1 A→C
    move disc 2 A→B
    hanoi(1, C→B)      move disc 1 C→B
  move disc 3 A→C
  hanoi(2, B→C)
    hanoi(1, B→A)      move disc 1 B→A
    move disc 2 B→C
    hanoi(1, A→C)      move disc 1 A→C

7 moves; the stack is at most 4 calls deep (3, 2, 1, and the empty call with 0 discs).

The math: recurrences and the master theorem

Hanoi. Let \(T(n)\) be the number of moves. Then \(T(0) = 0\) and \(T(n) = 2T(n-1) + 1\). Adding 1 to both sides, \(T(n) + 1 = 2\,(T(n-1) + 1)\), so \(T(n) + 1 = 2^n\) and

\[ T(n) = 2^n - 1. \]

No method can do better: the largest disc must move at least once, and before it does, the other \(n-1\) discs must all be on the spare peg, which costs at least \(T(n-1)\); afterwards they must come back, another \(T(n-1)\). With 64 discs and one move per second this takes about 585 billion years.

Correctness by induction. If hanoi(n-1, ...) is correct, then hanoi(n, ...) is: when disc \(n\) moves, every smaller disc is on the spare peg, so source and target hold no smaller disc.

The master theorem solves divide-and-conquer recurrences \(T(n) = a\,T(n/b) + f(n)\) with \(a \ge 1\), \(b > 1\). Compare \(f(n)\) with \(n^{\log_b a}\):

\[ T(n) = \begin{cases} \Theta\!\left(n^{\log_b a}\right) & \text{if } f(n) = O\!\left(n^{\log_b a - \varepsilon}\right) \text{ for some } \varepsilon > 0,\\[4pt] \Theta\!\left(n^{\log_b a} \log n\right) & \text{if } f(n) = \Theta\!\left(n^{\log_b a}\right),\\[4pt] \Theta\!\left(f(n)\right) & \text{if } f(n) = \Omega\!\left(n^{\log_b a + \varepsilon}\right) \text{ and } a f(n/b) \le c f(n),\ c<1. \end{cases} \]

Recurrence	Example	Answer
\(T(n) = T(n/2) + O(1)\)	binary search	\(\Theta(\log n)\)
\(T(n) = 2T(n/2) + O(n)\)	merge sort	\(\Theta(n \log n)\)
\(T(n) = 2T(n/2) + O(1)\)	sum of an array by halves	\(\Theta(n)\)
\(T(n) = 3T(n/2) + O(n)\)	Karatsuba multiplication	\(\Theta(n^{\log_2 3}) \approx \Theta(n^{1.585})\)
\(T(n) = T(n-1) + O(1)\)	factorial	\(\Theta(n)\) (not a master-theorem case)
\(T(n) = 2T(n-1) + O(1)\)	Hanoi	\(\Theta(2^n)\)

Watch it step by step

The three pegs as rows, discs listed from the bottom. Red is the disc that just moved.

Related ideas

• Tail recursion: when the recursive call is the very last action, a compiler can turn it into a loop. C++ compilers often do; Python and Java do not.
• Recursion to iteration: any recursion can be rewritten with an explicit stack, which is how deep DFS is made safe.
• Memoization turns exponential recursion into polynomial time when the same subproblems repeat: the starting point of dynamic programming.
• Mutual recursion: two functions that call each other, as in recursive-descent parsers.

See also

• Merge sort and quicksort: divide and conquer
• Fibonacci and the DP idea: when recursion repeats itself
• Backtracking: recursion that explores choices

References

• T. H. Cormen et al., Introduction to Algorithms, 4th ed., Chapter 4 (divide and conquer, the master theorem).
• R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics, 2nd ed., §1.1 (the Tower of Hanoi).
• É. Lucas published the Tower of Hanoi puzzle in 1883 under the name "N. Claus de Siam".