Tower of hanoi

Tower of Hanoi — The Problem That Teaches You to Think in Recursion

Most articles give you the algorithm. This one tries to give you the intuition — the moment where it actually clicks.

I remember the first time I encountered Tower of Hanoi in a DAA class. The formula was on the board — $T(n)=2^n-1$ — and I nodded along like everyone else. I could reproduce the steps. I could even trace the recursion tree.

But I didn't get it.

The thing is, Tower of Hanoi isn't really a disk-moving puzzle. It's a lesson in trusting the recursion — and that's a skill that pays dividends across every hard problem you'll ever face in DSA. Once this one clicks, divide-and-conquer problems stop feeling like magic and start feeling obvious.

So let's do this differently.

The Setup

Three pegs: A (source), B (auxiliary), C (destination).

n disks on peg A, stacked largest-to-smallest.

Goal: Move all disks to peg C.

Rules:

• Move only one disk at a time.

• Never place a larger disk on a smaller one.

• Use peg B however you like.

Simple rules. Surprisingly deep problem.

The Trap Most People Fall Into

The natural instinct when you see this problem is to simulate. "Okay, for 3 disks: move top disk to C, then... wait, no — move to B... then..."

You end up managing state in your head, getting confused around move 4 or 5, and convincing yourself recursion is somehow "magic."

It's not magic. There's one key shift in mindset:

Stop thinking about what you're doing right now. Think about what you're going to assume is already solved.

The Recursive Leap of Faith

Here's the actual insight:

Suppose you have n disks and you want to move them from A → C.

What if I told you: "Forget about the bottom disk. Pretend someone else has already solved the n-1 case."

If that's true, here's what you do:

1. Use that "someone" to move the top n-1 disks from A → B (using C as scratch)

2. Move the biggest disk from A → C (it's now free — nothing is on top of it)

3. Use that "someone" again to move n-1 disks from B → C (using A as scratch)

That's it. That's the whole algorithm.

The "someone" is just... you. On a smaller input. That's what recursion means.

Recurrence Relation

Each call to TOH(n) makes two calls to TOH(n-1) plus one move:

Base case:

Solving:

For n = 10, that's 1023 moves. For n = 64 (the mythological version of this puzzle), that's over 18 quintillion moves. The universe will end first.

Recursion Tree (n = 3)

Notice how the tree isn't just a diagram — it's a map of every subproblem. Each node is a "move n disks from X to Y" trust statement. The leaves are the base case: a single disk, which is trivially solvable.

The Algorithm

TOH(n, source, auxiliary, destination):
    if n == 1:
        print("Move disk 1 from", source, "to", destination)
        return

    TOH(n-1, source, destination, auxiliary)   // Move n-1 disks out of the way
    print("Move disk", n, "from", source, "to", destination)  // Move the big one
    TOH(n-1, auxiliary, source, destination)   // Stack n-1 on top

Pay attention to the parameter order. The second call swaps source and auxiliary — that's not a typo, that's the whole trick. The auxiliary becomes the new source, and the old source becomes the scratch space.

Full Trace: n = 3

Total: $2^3-1=7$ moves. ✓

Notice that move 4 is the "big disk" move — the one that could only happen after moves 1–3 cleared the way, and which sets up moves 5–7 to complete the job. The structure is self-similar at every level.

Complexity

Time complexity is unavoidable — the lower bound is provably $2^n-1$ moves. You can't do better; every disk must move at least once, and moving a disk k levels deep requires solving the $k-1$ subproblem twice.

Space is just the depth of the call stack, which is n.

Why This Problem Actually Matters

Tower of Hanoi isn't in your DAA curriculum as a historical curiosity. It's there because:

1. It's the simplest non-trivial recursive problem — the base case and recursive step are both obvious once you see them, making it ideal for building intuition.

2. It models the call stack explicitly — tracing the recursion tree by hand and mapping it to actual stack frames is one of the clearest mental models you'll build early on.

3. The "trust the recursion" mindset transfers directly to harder problems — merge sort, tree traversal, divide-and-conquer DP. All of them ask you to assume the sub-problem is solved and just handle the current level.

If you can explain why the parameter order in the second recursive call swaps source and auxiliary, without looking at the code — you've genuinely understood recursion, not just memorized it.

Quick Self-Test

Before moving on, try to answer these without scrolling back up:

• Q1: For n = 4, how many total moves?

• Q2: In TOH(n-1, auxiliary, source, destination) — why is source now the auxiliary and not the destination?

• Q3: What is the height of the recursion tree for n = 5?

(Answers: 15 moves, because after placing the nth disk on C, we need to move n-1 disks from B to C using A as scratch — so B is source, A is auxiliary, C is destination. Height = n = 5.)

Related Notes

These notes from my DAA series connect directly to what we covered here:

• Algorithm Basics — what makes an algorithm an algorithm

• Asymptotic Notation — how to read and write O(2ⁿ) properly

• Binary Search Recurrence Relation — solving recurrences like T(n) = 2T(n-1) + 1

• Merge Sort — divide-and-conquer done iteratively

• Quick Sort — another classic D&C problem

• Dynamic Programming: 0/1 Knapsack — when recursion + memoization is the answer

• Fraction Knapsack (Greedy) — for comparison with D&C approaches

• Minimax using Divide and Conquer

• Full DAA Notes Index

External References

• Tower of Hanoi — Wikipedia — mathematical proof of optimality and iterative solutions

• Visualgo: Recursion Visualization — watch the call stack animate in real time (genuinely useful)

• CLRS (Introduction to Algorithms) — Chapter on divide and conquer for the formal treatment

• CS50 Lecture on Recursion — David Malan's explanation is the gold standard for building intuition

Part of the DAA Design and Analysis series on NoteHub.