Recursion

Moving a Tower of Hanoi of 64 disks takes 18,446,744,073,709,551,615 moves; a recursive function describes the solution in four lines.

A function that calls itself

Some problems contain a smaller copy of themselves. The factorial of 5, written 5!, is 5 × 4 × 3 × 2 × 1 = 120. Look at it again: it is 5 × (4 × 3 × 2 × 1), which is 5 × 4!. In general n! = n × (n − 1)!, so to compute a factorial you can compute a smaller factorial and multiply. A function that solves a problem by calling itself on a smaller version is recursive.

function factorial(n) {
  if (n <= 1) return 1;          // base case: stop here
  return n * factorial(n - 1);   // recursive case: a smaller problem
}
console.log(factorial(5)); // 120

Every recursive function needs two parts. The base case is an input small enough to answer directly, without another call: here, the factorial of 1 is 1. The recursive case reduces the problem and calls the function again. Each call must move closer to the base case. If it does not, for example if you wrote factorial(n + 1) by mistake, the calls never end.

The call stack

How does the computer keep track of all those unfinished calls? When factorial(5) runs, it reaches 5 * factorial(4) and has to wait for the answer. The computer puts the waiting call on a stack, a pile where the last item placed is the first one taken off. factorial(4) waits for factorial(3), and so on down to factorial(1), which returns 1 straight away. Then the stack unwinds: factorial(2) returns 2, factorial(3) returns 6, factorial(4) returns 24, and factorial(5) returns 120.

The stack has a limited size. A recursion that never reaches its base case keeps adding calls until the space runs out, and JavaScript stops with an error; in Chrome and Node.js the message is "RangeError: Maximum call stack size exceeded". The same limit means that very deep recursion, hundreds of thousands of levels, is better written as a loop.

The Tower of Hanoi

The Tower of Hanoi is a puzzle published by the French mathematician Édouard Lucas in 1883. There are three pegs and a stack of disks of different sizes on the first peg, largest at the bottom. The goal is to move the whole stack to the third peg. You may move only one disk at a time, only the top disk of a peg, and never put a larger disk on a smaller one.

Thinking step by step about where each disk goes gets confusing quickly. Thinking recursively makes it short. To move n disks from A to C: first move the top n − 1 disks out of the way, from A to B. Then move the largest disk from A to C. Then move the n − 1 disks from B onto it at C. Moving n − 1 disks is the same puzzle, one size smaller, and moving one disk is the base case. For 3 disks this gives 7 moves; the lab shows the stack of waiting calls at every move.

function hanoi(n, from, to, via) {
  if (n === 0) return;
  hanoi(n - 1, from, via, to);
  console.log("disk " + n + ": " + from + " -> " + to);
  hanoi(n - 1, via, to, from);
}
hanoi(3, "A", "C", "B");  // 7 moves

How many moves does n disks take? Moving n disks costs two moves of n − 1 disks plus one: M(n) = 2M(n − 1) + 1, with M(1) = 1. That gives 1, 3, 7, 15, 31, so M(n) = 2ⁿ − 1, and no solution can use fewer. Ten disks take 1,023 moves. Sixty-four disks take 2⁶⁴ − 1 = 18,446,744,073,709,551,615 moves; at one move per second that is about 585 billion years. This is the O(2ⁿ) growth from the last unit.

Recursion, loops and repeated work

Anything written with recursion can be written with a loop and a stack of your own, and simple cases such as factorial are often clearer as loops. Recursion shines when the problem itself is shaped like a tree: splitting a list in merge sort, exploring folders inside folders, or searching a maze, which is the topic of the last unit. One trap is repeated work. The Fibonacci numbers 0, 1, 1, 2, 3, 5, 8, … follow fib(n) = fib(n − 1) + fib(n − 2). Written directly as recursion, fib(10) = 55 makes 177 calls, fib(20) makes 21,891, and fib(30) makes 2,692,537, because the same smaller values are computed again and again. Remembering answers already found, or building up from the bottom with a loop, removes that waste.