Classic Recursion Puzzles

The problem

Three pegs. A stack of disks sorted big-to-small on the first peg. Move the whole stack to the third peg, one disk at a time, never placing a bigger disk on a smaller one. With three disks you can muddle through by trial and error. With ten disks you will lose the plot before you are halfway.

Then there is the campfire version: n people stand in a circle, and every k-th person is eliminated until one survivor remains. Where should you stand to be the last one left? Both puzzles feel like they demand you track a hopeless amount of state — and both collapse to a few lines once you find the recursive handle.

A first attempt

Try to plan Hanoi as one flat sequence of moves and you drown. You would have to hold the position of every disk in your head and reason about all of them at once — the state space is enormous, and there is no obvious loop that produces the moves in order. People genuinely get stuck here.

For Josephus, the brute-force fix is to actually simulate the circle: put n people in a list and repeatedly delete every k-th one. That works, but deleting from a list is O(n) each time and you do it n times, giving O(n²) — sluggish for large circles, and it teaches you nothing about why the survivor lands where it does.

The insight

Both puzzles contain a smaller copy of themselves — the signature of recursion.

Hanoi: to move n disks from source to destination, first move the top n − 1 disks out of the way onto the spare peg, move the single largest disk across, then move those n − 1 disks on top of it. You never plan the whole thing — you defer the hard part to a smaller Hanoi.

Josephus: solve the circle of n − 1 survivors first, then figure out how that answer shifts once you add the person who gets eliminated first. If josephus(n − 1, k) gives the survivor's position in the smaller circle, the answer for n is (josephus(n − 1, k) + k) % n. The + k accounts for counting starting past the first victim.

How it works

hanoi(3, A, B, C):
  hanoi(2, A, C, B)      move 2 disks A -> B (using C)
  move disk 3: A -> C
  hanoi(2, B, A, C)      move 2 disks B -> C (using A)

josephus(1, k) = 0
josephus(2, k) = (0 + k) % 2
josephus(3, k) = (josephus(2,k) + k) % 3
...

The code

Hanoi returns the move count; Josephus returns the 0-indexed survivor (add 1 for a human-friendly seat number).

def hanoi(n, src, aux, dst):
    if n == 0:
        return
    hanoi(n - 1, src, dst, aux)
    print(f"Move disk {n}: {src} -> {dst}")
    hanoi(n - 1, aux, src, dst)


def josephus(n, k):            # 0-indexed survivor
    if n == 1:
        return 0
    return (josephus(n - 1, k) + k) % n


hanoi(3, 'A', 'B', 'C')
print(josephus(7, 3))  # 3  (seat 4 for 1-indexed)

function hanoi(n: number, src: string, aux: string, dst: string): void {
  if (n === 0) return;
  hanoi(n - 1, src, dst, aux);
  console.log(`Move disk ${n}: ${src} -> ${dst}`);
  hanoi(n - 1, aux, src, dst);
}

function josephus(n: number, k: number): number {
  if (n === 1) return 0;
  return (josephus(n - 1, k) + k) % n;
}

hanoi(3, "A", "B", "C");
console.log(josephus(7, 3)); // 3

static void hanoi(int n, char src, char aux, char dst) {
    if (n == 0) return;
    hanoi(n - 1, src, dst, aux);
    System.out.println("Move disk " + n + ": " + src + " -> " + dst);
    hanoi(n - 1, aux, src, dst);
}

static int josephus(int n, int k) {   // 0-indexed survivor
    if (n == 1) return 0;
    return (josephus(n - 1, k) + k) % n;
}

// hanoi(3, 'A', 'B', 'C');  josephus(7, 3) -> 3

#include <stdio.h>

void hanoi(int n, char src, char aux, char dst) {
    if (n == 0) return;
    hanoi(n - 1, src, dst, aux);
    printf("Move disk %d: %c -> %c\n", n, src, dst);
    hanoi(n - 1, aux, src, dst);
}

int josephus(int n, int k) {          /* 0-indexed survivor */
    if (n == 1) return 0;
    return (josephus(n - 1, k) + k) % n;
}

/* hanoi(3, 'A', 'B', 'C');  josephus(7, 3) -> 3 */

#include <iostream>

void hanoi(int n, char src, char aux, char dst) {
    if (n == 0) return;
    hanoi(n - 1, src, dst, aux);
    std::cout << "Move disk " << n << ": " << src << " -> " << dst << "\n";
    hanoi(n - 1, aux, src, dst);
}

int josephus(int n, int k) {          // 0-indexed survivor
    if (n == 1) return 0;
    return (josephus(n - 1, k) + k) % n;
}

// hanoi(3, 'A', 'B', 'C');  josephus(7, 3) -> 3

Complexity

Hanoi is provably exponential — moving n disks requires exactly 2ⁿ − 1 moves, no shortcut exists. Josephus, by contrast, drops from the O(n²) simulation to a clean O(n) once you recurse on position instead of simulating the circle.

When to use it

Practice

Recap

• Both puzzles dissolve once you spot the smaller self-similar copy inside them.
• Tower of Hanoi is inherently O(2ⁿ) — exactly 2ⁿ − 1 moves — and models divide-and-conquer.
• Recursing on position turns the Josephus simulation from O(n²) into an O(n) formula.