Loading…

easyBacktrackingSometimes asked

Tower of Hanoi

Q: How do you solve Tower of Hanoi using the Closed-Form Move Count (Count Only) approach?

When to use it: Use when the interviewer asks only 'how many moves?' — answer 2ⁿ - 1 instantly and derive it. When only the count matters, skip the simulation. **Set up the recurrence.** To move `n` disks you move `n-1` disks twice (off, then back) and the bottom disk once: `T(n) = 2·T(n-1) + 1`, with `T(0) = 0`. **Solve it.** Unrolling gives `T(n) = 1 + 2 + 4 + … + 2^{n-1} = 2ⁿ - 1`. So the answer is `(1 << n) - 1`. **Why it's worth saying.** Producing the closed form shows you understand the structure rather than just coding the recursion. If the task is purely the count, this is O(1) versus O(2ⁿ) for emitting every move. **When it's not enough.** If the interviewer wants the actual sequence of moves, you still need the recursion below — the closed form only gives the total. Time complexity: O(1). Space complexity: O(1).

Q: How do you solve Tower of Hanoi using the Recursive Move Generation (Optimal Sequence) approach?

When to use it: The main answer when moves must be emitted. Phrase it as 'move n-1 to the spare, move the big disk, move n-1 onto it'. Solve the puzzle by reducing it to two copies of the same puzzle with one fewer disk. **The decomposition.** Moving `n` disks from `source` to `target` is impossible directly while the bottom disk is buried, so: (1) move the top `n-1` disks from `source` to `auxiliary`, freeing the bottom disk; (2) move disk `n` from `source` to `target`; (3) move the `n-1` disks from `auxiliary` to `target`, landing them on the bottom disk. **The rotating helper peg.** The key subtlety is which peg serves as the spare. In step 1 you're parking on `auxiliary`, so `target` temporarily plays the helper role — the recursive call is `hanoi(n-1, source, target, auxiliary)`. In step 3 you're moving off `auxiliary` onto `target`, so `source` plays helper — the call is `hanoi(n-1, auxiliary, source, target)`. Getting these argument orders right is the whole correctness story. **Why moves are always legal.** Because each recursive call relocates a complete, correctly ordered sub-stack before the larger disk underneath ever moves, a bigger disk is never placed on a smaller one. You don't need to check disk sizes at runtime; the recursion structure enforces the rule. **The base case.** `n == 0` returns without doing anything — there's nothing to move. (Writing the base at `n == 1` with one direct move is equivalent and just stops one level earlier.) Time complexity: O(2ⁿ). Space complexity: O(n).

Backtracking · 10 of 13 · 8 min

You have three pegs — a source, an auxiliary, and a target — and n disks of distinct sizes stacked on the source peg in decreasing size (largest at the bottom).

Move all n disks to the target peg under two rules: move only one disk at a time (always the top disk of a peg), and never place a larger disk on top of a smaller one.

Print each move as Move disk k from X to Y, and return the total number of moves made.

In plain English

The puzzle reduces by one disk: to move n disks, you must first get the top n-1 out of the way onto the spare peg, move the bottom disk, then restack the n-1 on top. That self-similar structure is exactly recursion. The total move count is fixed at 2ⁿ - 1 for the optimal sequence.

Examples

Example 1

Input: n = 1, pegs A→C (aux B)
Output: Move disk 1 from A to C (1 move)
Note: A single disk goes straight to the target. 2¹ - 1 = 1.

Example 2

Input: n = 2, pegs A→C (aux B)
Output: disk 1 A→B, disk 2 A→C, disk 1 B→C (3 moves)
Note: Park the small disk on B, move the large disk to C, restack the small disk. 2² - 1 = 3.

Example 3

Input: n = 3, pegs A→C (aux B)
Output: 7 moves total
Note: 2³ - 1 = 7: the sequence A→C, A→B, C→B, A→C, B→A, B→C, A→C.

Constraints

1 ≤ n ≤ 20 (so the move count 2ⁿ - 1 stays printable)
Exactly 3 pegs, labeled by name (e.g. 'A', 'B', 'C')
Disks start sorted largest-on-bottom on the source peg
The minimum number of moves is 2ⁿ - 1

Clarifying questions4First question: Do I print the moves, count them, or both?Explore questions

Q1.Do I print the moves, count them, or both?
I'll print each move and also return the count. If only the count is wanted, the closed form 2ⁿ - 1 answers it instantly.
Q2.How are the pegs identified?
By labels like 'A' (source), 'B' (auxiliary), 'C' (target). The recursion just permutes which label plays which role.
Q3.Is three pegs fixed?
Yes. With four or more pegs the optimal count follows the Frame-Stewart algorithm, which is a different problem.
Q4.How large can n be?
Up to 20 here, so 2²⁰ - 1 ≈ a million moves — large but printable. Beyond that, emitting every move is impractical.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Move n disks from the source peg to the target peg using one auxiliary peg, never placing a larger disk on a smaller one. The recursive solution: move the top n-1 disks from source to auxiliary, move the largest disk from source to target, then move those n-1 disks from auxiliary to target. The minimum number of moves is exactly 2ⁿ - 1, and the recursion prints them in order.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can express the three-step recursion cleanly, get the peg arguments right, and state the 2ⁿ - 1 move count with its recurrence.

Where candidates slip

Mixing up which peg is the helper in each recursive call, or stating the move count as 2ⁿ or n! instead of 2ⁿ - 1.

How to stand out

Write the three lines crisply, explain why the auxiliary peg swaps roles between the two calls, and derive 2ⁿ - 1 from T(n) = 2T(n-1) + 1.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Closed-Form Move Count (Count Only)	`O(1)`	`O(1)`	Use when the interviewer asks only 'how many moves?' — answer 2ⁿ - 1 instantly and derive it.	Read
2	Recursive Move Generation (Optimal Sequence)Optimal	`O(2ⁿ)`	`O(n)`	The main answer when moves must be emitted. Phrase it as 'move n-1 to the spare, move the big disk, move n-1 onto it'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewMove n disks A → CNeed the move sequence?Count onlyYes, every moveExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Closed-Form Move Count (Count Only)

TimeO(1)SpaceO(1)

Use when the interviewer asks only 'how many moves?' — answer 2ⁿ - 1 instantly and derive it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Let T(n) be the minimum moves for n disks. How many sub-moves does moving the n-1 stack twice cost, plus the one big-disk move?

2Hint 2Explore hint

T(n) = 2·T(n-1) + 1 with T(0) = 0. Expand it a few times.

3Hint 3Explore hint

The recurrence solves to T(n) = 2ⁿ - 1 — compute it directly as (1 << n) - 1.

A · Core idea

When only the count matters, skip the simulation.

Set up the recurrence. To move n disks you move n-1 disks twice (off, then back) and the bottom disk once: T(n) = 2·T(n-1) + 1, with T(0) = 0.

Solve it. Unrolling gives T(n) = 1 + 2 + 4 + … + 2^{n-1} = 2ⁿ - 1. So the answer is (1 << n) - 1.

Why it's worth saying. Producing the closed form shows you understand the structure rather than just coding the recursion. If the task is purely the count, this is O(1) versus O(2ⁿ) for emitting every move.

When it's not enough. If the interviewer wants the actual sequence of moves, you still need the recursion below — the closed form only gives the total.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 3

Array state

n=1,2

1, 3

[0]

n ↓

[1]

Current pointerResolved stateNot processed

Final result7

C · Code with teaching comments

Reference implementation previewpublic long minMoves(int n) { return (1L << n) - 1; // 2^n - 1 }Explore the full code

solution.javaJava

Closed-Form Move Count (Count Only) — reference

1 teaching note

1
public long minMoves(int n) {
2
    // Closed form of T(n) = 2T(n-1) + 1; use a long so n up to 20 (and beyond) doesn't
3
    // overflow.
4
    return (1L << n) - 1; // 2^n - 1
5
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.5 lines

D · Why it works and complexityO(1) timeO(1) spaceOpen the invariant and proofExplore the proof

The recurrence T(n) = 2T(n-1) + 1 is a geometric sum in disguise. Recognizing that 'do the subproblem twice plus a constant' yields 2ⁿ - 1 is a transferable skill for analyzing any doubling recursion.

ComplexityO(1) time, O(1) space — Evaluating 2ⁿ - 1 is a single shift and subtraction — constant time and space, no recursion.

E · Edge cases and pitfalls3Quoting 2ⁿ or n! instead of 2ⁿ - 1.Explore edge cases

Pitfalls

Quoting 2ⁿ or n! instead of 2ⁿ - 1.
Overflowing a 32-bit int for larger n — use 64-bit or big integers.
Giving only the count when the question actually wants the move sequence.

03.2

Approach 2 of 2 · Optimal

Recursive Move Generation (Optimal Sequence)

TimeO(2ⁿ)SpaceO(n)

The main answer when moves must be emitted. Phrase it as 'move n-1 to the spare, move the big disk, move n-1 onto it'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

To move n disks from source to target, what must happen to the top n-1 disks before the bottom disk can move?

2Hint 2Explore hint

Recursively move n-1 disks from source to auxiliary (target acts as the spare), then move disk n from source to target.

3Hint 3Explore hint

Finally move the n-1 disks from auxiliary to target (source now acts as the spare). The base case n == 0 does nothing.

A · Core idea

Solve the puzzle by reducing it to two copies of the same puzzle with one fewer disk.

The decomposition. Moving n disks from source to target is impossible directly while the bottom disk is buried, so: (1) move the top n-1 disks from source to auxiliary, freeing the bottom disk; (2) move disk n from source to target; (3) move the n-1 disks from auxiliary to target, landing them on the bottom disk.

The rotating helper peg. The key subtlety is which peg serves as the spare. In step 1 you're parking on auxiliary, so target temporarily plays the helper role — the recursive call is hanoi(n-1, source, target, auxiliary). In step 3 you're moving off auxiliary onto target, so source plays helper — the call is hanoi(n-1, auxiliary, source, target). Getting these argument orders right is the whole correctness story.

Why moves are always legal. Because each recursive call relocates a complete, correctly ordered sub-stack before the larger disk underneath ever moves, a bigger disk is never placed on a smaller one. You don't need to check disk sizes at runtime; the recursion structure enforces the rule.

The base case. n == 0 returns without doing anything — there's nothing to move. (Writing the base at n == 1 with one direct move is equivalent and just stops one level earlier.)

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 2, hanoi(2, A, B, C)

Interactive diagram

Recursion tree for n = 2

hanoi(2,A,B,C)

Active call / nodeSupporting contextReturned stateNot active

The middle node is the bottom-disk move; left and right subtrees move the n-1 stack.

Final resultA→B, A→C, B→C (3 moves)

C · Code with teaching comments

solution.javaJava

Recursive Move Generation (Optimal Sequence) — optimal

4 teaching notes

1
public int towerOfHanoi(int n, char from, char aux, char to) {
2
    // Nothing to move with zero disks — the recursion's stop.
3
    if (n == 0) return 0;
4
    int moves = 0;
5
    // Move the top n-1 disks aside; note 'to' is passed as the auxiliary here.
6
    moves += towerOfHanoi(n - 1, from, to, aux); // park n-1 on aux (to is helper)
7
    // The single legal move of the largest disk now exposed.
8
    System.out.println("Move disk " + n + " from " + from + " to " + to);
9
    moves += 1;
10
    // Restack the n-1 disks onto the target; now 'from' is the auxiliary.
11
    moves += towerOfHanoi(n - 1, aux, from, to); // bring n-1 to target (from is helper)
12
    return moves;
13
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.13 lines

D · Why it works and complexityO(2ⁿ) timeO(n) spaceOpen the invariant and proofExplore the proof

The puzzle is self-similar: an n-disk move is literally two (n-1)-disk moves wrapped around a single disk move. The only thing that changes between the two sub-calls is which peg is the spare — recognizing that role rotation is what makes the three-line solution click.

ComplexityO(2ⁿ) time, O(n) space — The recurrence T(n) = 2T(n-1) + 1 = 2ⁿ - 1 means 2ⁿ - 1 moves are printed, so time is O(2ⁿ). The recursion depth is n, so the call stack is O(n).

E · Edge cases and pitfalls7n = 0 — Base case returns 0 immediately; no moves printed.Explore edge cases

Edge cases handled

n = 0Base case returns 0 immediately; no moves printed.
n = 1Skips both recursive calls' work, prints one move, returns 1.
n = 20Prints 2²⁰ - 1 = 1,048,575 moves; recursion depth only 20.
swapped peg labelsOutput relabels source/target consistently; the move structure is identical.

Pitfalls

Passing the helper peg in the wrong argument slot, producing illegal moves.
Forgetting the base case, causing infinite recursion / stack overflow.
Trying to track disk sizes manually instead of trusting the recursion's ordering.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int towerOfHanoi(int n, char from, char aux, char to) { if (n == 0) return 0; int moves = 0; moves += towerOfHanoi(n - 1, from, to, aux); // park n-1 on aux (to is helper) System.out.println("Move disk " + n + " from " + from + " to " + to);Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Wrong helper peg in a recursive call

If the second call reuses the original (source, aux, target) order instead of rotating the helper, disks land on the wrong peg and the sequence becomes illegal.

Explore the code comparison

Don't write this

self.towerOfHanoi(n - 1, frm, to, aux)
print(...)
self.towerOfHanoi(n - 1, frm, aux, to)  # WRONG: should start from aux

Write this instead

self.towerOfHanoi(n - 1, frm, to, aux)
print(...)
self.towerOfHanoi(n - 1, aux, frm, to)  # move from aux, source is helper

Wrong move-count formula

The recurrence T(n) = 2T(n-1) + 1 sums to 2ⁿ - 1, not 2ⁿ; an off-by-one here is a classic slip under pressure.

Explore the code comparison

Don't write this

return (1L << n); // 2^n — one too many

Write this instead

return (1L << n) - 1; // 2^n - 1

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Recursive divide-and-conquer: shift n-1 aside, move 1, shift n-1 back

Code pattern to memorize

hanoi(n, from, aux, to):
    if n == 0: return
    hanoi(n - 1, from, to, aux)   # park n-1 on aux
    move disk n: from -> to
    hanoi(n - 1, aux, from, to)   # bring n-1 to target
# minimum moves T(n) = 2^n - 1

Rules to remember

1Base case n == 0 does nothing — the cleanest stop; some write n == 1 as one direct move.
2The auxiliary peg rotates: in the first call to plays helper; in the second call from plays helper.
3Minimum moves satisfy T(n) = 2·T(n-1) + 1 = 2ⁿ - 1 — quote this when asked for the count.
4You never need to track disk sizes explicitly; the recursion order guarantees a small disk is always moved off first.
5Don't swap the peg arguments — passing them in the wrong order silently produces illegal moves.

Use this pattern when

Teaching or testing clean recursion and the recurrence T(n) = 2T(n-1) + 1
Problems that decompose into 'do a smaller version, one action, another smaller version'
Demonstrating exponential blow-up from a simple recurrence
Generating the exact move sequence for a stacked-relocation puzzle

Choose another pattern when

You only need the move COUNT → use the closed form 2ⁿ - 1, skip the recursion
n is large and you must emit every move → 2ⁿ - 1 moves is infeasible to print
More than 3 pegs (Frame-Stewart) → the optimal count changes; this recurrence no longer applies
State-search problems → BFS/DFS over states, not this fixed recurrence

Interview takeaway

Tower of Hanoi is the textbook divide-and-conquer recursion: park n-1 disks on the spare peg, move the biggest, then bring the n-1 back. The recurrence 2T(n-1)+1 gives the famous 2ⁿ - 1 minimum moves.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternTower of Hanoi is the archetypal divide-and-conquer recursion: solve n-1 twice around a single move, giving T(n) = 2T(n-1) + 1 = 2ⁿ - 1. The role-rotating recursive calls are the same shape as many self-similar recursions.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Tower of Hanoi with 4 Pegs (Frame-Stewart)
Coming soon
An extra peg changes the optimal count; the Frame-Stewart algorithm splits the stack to minimize moves.
Iterative Tower of Hanoi
Coming soon
For odd/even n, repeatedly make the only two legal moves in a fixed cycle to avoid recursion.
K-th Symbol in Grammar
Coming soon
Another self-similar recursion where the answer depends on the position within a doubling structure.
Pow(x, n)
Coming soon
Divide-and-conquer recursion with a doubling structure, analyzed via a similar recurrence.

Same pattern

←

Rat in a Maze

Continue · Next problem

Crossword Puzzle

easyBacktrackingSometimes asked

Tower of Hanoi

Backtracking · 10 of 13 · 8 min

You have three pegs — a source, an auxiliary, and a target — and n disks of distinct sizes stacked on the source peg in decreasing size (largest at the bottom).

Move all n disks to the target peg under two rules: move only one disk at a time (always the top disk of a peg), and never place a larger disk on top of a smaller one.

Print each move as Move disk k from X to Y, and return the total number of moves made.

In plain English

Examples

Example 1

Input: n = 1, pegs A→C (aux B)
Output: Move disk 1 from A to C (1 move)
Note: A single disk goes straight to the target. 2¹ - 1 = 1.

Example 2

Input: n = 2, pegs A→C (aux B)
Output: disk 1 A→B, disk 2 A→C, disk 1 B→C (3 moves)
Note: Park the small disk on B, move the large disk to C, restack the small disk. 2² - 1 = 3.

Example 3

Input: n = 3, pegs A→C (aux B)
Output: 7 moves total
Note: 2³ - 1 = 7: the sequence A→C, A→B, C→B, A→C, B→A, B→C, A→C.

Constraints

1 ≤ n ≤ 20 (so the move count 2ⁿ - 1 stays printable)
Exactly 3 pegs, labeled by name (e.g. 'A', 'B', 'C')
Disks start sorted largest-on-bottom on the source peg
The minimum number of moves is 2ⁿ - 1

Clarifying questions4First question: Do I print the moves, count them, or both?Explore questions

Q1.Do I print the moves, count them, or both?
I'll print each move and also return the count. If only the count is wanted, the closed form 2ⁿ - 1 answers it instantly.
Q2.How are the pegs identified?
By labels like 'A' (source), 'B' (auxiliary), 'C' (target). The recursion just permutes which label plays which role.
Q3.Is three pegs fixed?
Yes. With four or more pegs the optimal count follows the Frame-Stewart algorithm, which is a different problem.
Q4.How large can n be?
Up to 20 here, so 2²⁰ - 1 ≈ a million moves — large but printable. Beyond that, emitting every move is impractical.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can express the three-step recursion cleanly, get the peg arguments right, and state the 2ⁿ - 1 move count with its recurrence.

Where candidates slip

Mixing up which peg is the helper in each recursive call, or stating the move count as 2ⁿ or n! instead of 2ⁿ - 1.

How to stand out

Write the three lines crisply, explain why the auxiliary peg swaps roles between the two calls, and derive 2ⁿ - 1 from T(n) = 2T(n-1) + 1.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Closed-Form Move Count (Count Only)	`O(1)`	`O(1)`	Use when the interviewer asks only 'how many moves?' — answer 2ⁿ - 1 instantly and derive it.	Read
2	Recursive Move Generation (Optimal Sequence)Optimal	`O(2ⁿ)`	`O(n)`	The main answer when moves must be emitted. Phrase it as 'move n-1 to the spare, move the big disk, move n-1 onto it'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Closed-Form Move Count (Count Only)

TimeO(1)SpaceO(1)

Use when the interviewer asks only 'how many moves?' — answer 2ⁿ - 1 instantly and derive it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Let T(n) be the minimum moves for n disks. How many sub-moves does moving the n-1 stack twice cost, plus the one big-disk move?

2Hint 2Explore hint

T(n) = 2·T(n-1) + 1 with T(0) = 0. Expand it a few times.

3Hint 3Explore hint

The recurrence solves to T(n) = 2ⁿ - 1 — compute it directly as (1 << n) - 1.

A · Core idea

When only the count matters, skip the simulation.

Set up the recurrence. To move n disks you move n-1 disks twice (off, then back) and the bottom disk once: T(n) = 2·T(n-1) + 1, with T(0) = 0.

Solve it. Unrolling gives T(n) = 1 + 2 + 4 + … + 2^{n-1} = 2ⁿ - 1. So the answer is (1 << n) - 1.

When it's not enough. If the interviewer wants the actual sequence of moves, you still need the recursion below — the closed form only gives the total.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 3

Array state

n=1,2

1, 3

[0]

n ↓

[1]

Current pointerResolved stateNot processed

Final result7

C · Code with teaching comments

Reference implementation previewpublic long minMoves(int n) { return (1L << n) - 1; // 2^n - 1 }Explore the full code

solution.javaJava

Closed-Form Move Count (Count Only) — reference

1 teaching note

1
public long minMoves(int n) {
2
    // Closed form of T(n) = 2T(n-1) + 1; use a long so n up to 20 (and beyond) doesn't
3
    // overflow.
4
    return (1L << n) - 1; // 2^n - 1
5
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.5 lines

D · Why it works and complexityO(1) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(1) time, O(1) space — Evaluating 2ⁿ - 1 is a single shift and subtraction — constant time and space, no recursion.

E · Edge cases and pitfalls3Quoting 2ⁿ or n! instead of 2ⁿ - 1.Explore edge cases

Pitfalls

Quoting 2ⁿ or n! instead of 2ⁿ - 1.
Overflowing a 32-bit int for larger n — use 64-bit or big integers.
Giving only the count when the question actually wants the move sequence.

03.2

Approach 2 of 2 · Optimal

Recursive Move Generation (Optimal Sequence)

TimeO(2ⁿ)SpaceO(n)

The main answer when moves must be emitted. Phrase it as 'move n-1 to the spare, move the big disk, move n-1 onto it'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

To move n disks from source to target, what must happen to the top n-1 disks before the bottom disk can move?

2Hint 2Explore hint

Recursively move n-1 disks from source to auxiliary (target acts as the spare), then move disk n from source to target.

3Hint 3Explore hint

Finally move the n-1 disks from auxiliary to target (source now acts as the spare). The base case n == 0 does nothing.

A · Core idea

Solve the puzzle by reducing it to two copies of the same puzzle with one fewer disk.

The base case. n == 0 returns without doing anything — there's nothing to move. (Writing the base at n == 1 with one direct move is equivalent and just stops one level earlier.)

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 2, hanoi(2, A, B, C)

Interactive diagram

Recursion tree for n = 2

hanoi(2,A,B,C)

Active call / nodeSupporting contextReturned stateNot active

The middle node is the bottom-disk move; left and right subtrees move the n-1 stack.

Final resultA→B, A→C, B→C (3 moves)

C · Code with teaching comments

solution.javaJava

Recursive Move Generation (Optimal Sequence) — optimal

4 teaching notes

1
public int towerOfHanoi(int n, char from, char aux, char to) {
2
    // Nothing to move with zero disks — the recursion's stop.
3
    if (n == 0) return 0;
4
    int moves = 0;
5
    // Move the top n-1 disks aside; note 'to' is passed as the auxiliary here.
6
    moves += towerOfHanoi(n - 1, from, to, aux); // park n-1 on aux (to is helper)
7
    // The single legal move of the largest disk now exposed.
8
    System.out.println("Move disk " + n + " from " + from + " to " + to);
9
    moves += 1;
10
    // Restack the n-1 disks onto the target; now 'from' is the auxiliary.
11
    moves += towerOfHanoi(n - 1, aux, from, to); // bring n-1 to target (from is helper)
12
    return moves;
13
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.13 lines

D · Why it works and complexityO(2ⁿ) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(2ⁿ) time, O(n) space — The recurrence T(n) = 2T(n-1) + 1 = 2ⁿ - 1 means 2ⁿ - 1 moves are printed, so time is O(2ⁿ). The recursion depth is n, so the call stack is O(n).

E · Edge cases and pitfalls7n = 0 — Base case returns 0 immediately; no moves printed.Explore edge cases

Edge cases handled

n = 0Base case returns 0 immediately; no moves printed.
n = 1Skips both recursive calls' work, prints one move, returns 1.
n = 20Prints 2²⁰ - 1 = 1,048,575 moves; recursion depth only 20.
swapped peg labelsOutput relabels source/target consistently; the move structure is identical.

Pitfalls

Passing the helper peg in the wrong argument slot, producing illegal moves.
Forgetting the base case, causing infinite recursion / stack overflow.
Trying to track disk sizes manually instead of trusting the recursion's ordering.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Wrong helper peg in a recursive call

If the second call reuses the original (source, aux, target) order instead of rotating the helper, disks land on the wrong peg and the sequence becomes illegal.

Explore the code comparison

Don't write this

self.towerOfHanoi(n - 1, frm, to, aux)
print(...)
self.towerOfHanoi(n - 1, frm, aux, to)  # WRONG: should start from aux

Write this instead

self.towerOfHanoi(n - 1, frm, to, aux)
print(...)
self.towerOfHanoi(n - 1, aux, frm, to)  # move from aux, source is helper

Wrong move-count formula

The recurrence T(n) = 2T(n-1) + 1 sums to 2ⁿ - 1, not 2ⁿ; an off-by-one here is a classic slip under pressure.

Explore the code comparison

Don't write this

return (1L << n); // 2^n — one too many

Write this instead

return (1L << n) - 1; // 2^n - 1

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Recursive divide-and-conquer: shift n-1 aside, move 1, shift n-1 back

Code pattern to memorize

hanoi(n, from, aux, to):
    if n == 0: return
    hanoi(n - 1, from, to, aux)   # park n-1 on aux
    move disk n: from -> to
    hanoi(n - 1, aux, from, to)   # bring n-1 to target
# minimum moves T(n) = 2^n - 1

Rules to remember

1Base case n == 0 does nothing — the cleanest stop; some write n == 1 as one direct move.
2The auxiliary peg rotates: in the first call to plays helper; in the second call from plays helper.
3Minimum moves satisfy T(n) = 2·T(n-1) + 1 = 2ⁿ - 1 — quote this when asked for the count.
4You never need to track disk sizes explicitly; the recursion order guarantees a small disk is always moved off first.
5Don't swap the peg arguments — passing them in the wrong order silently produces illegal moves.

Use this pattern when

Teaching or testing clean recursion and the recurrence T(n) = 2T(n-1) + 1
Problems that decompose into 'do a smaller version, one action, another smaller version'
Demonstrating exponential blow-up from a simple recurrence
Generating the exact move sequence for a stacked-relocation puzzle

Choose another pattern when

You only need the move COUNT → use the closed form 2ⁿ - 1, skip the recursion
n is large and you must emit every move → 2ⁿ - 1 moves is infeasible to print
More than 3 pegs (Frame-Stewart) → the optimal count changes; this recurrence no longer applies
State-search problems → BFS/DFS over states, not this fixed recurrence

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Tower of Hanoi with 4 Pegs (Frame-Stewart)
Coming soon
An extra peg changes the optimal count; the Frame-Stewart algorithm splits the stack to minimize moves.
Iterative Tower of Hanoi
Coming soon
For odd/even n, repeatedly make the only two legal moves in a fixed cycle to avoid recursion.
K-th Symbol in Grammar
Coming soon
Another self-similar recursion where the answer depends on the position within a doubling structure.
Pow(x, n)
Coming soon
Divide-and-conquer recursion with a doubling structure, analyzed via a similar recurrence.

Same pattern

←

Rat in a Maze

Continue · Next problem

Crossword Puzzle