Medium–hard · recursion

Tower of Hanoi

This is the first problem where the answer is call yourself. It feels like cheating the first time. It isn't — it's the whole idea.

At a glanceMove n discs from A to C through B with three recursive calls — shift n−1 to the spare peg, move the last disc, shift n−1 back — for 2ⁿ − 1 moves in total.

Problem

Input: One integer n (1 ≤ n ≤ 8) — the number of discs, all starting on peg A.

Output: One move per line, in the form X->Y, moving the whole stack from A to C using B as spare. A larger disc may never sit on a smaller one.

Samples:

InputOutput
1A->C
2A->B
A->C
B->C
3A->C
A->B
C->B
A->C
B->A
B->C
A->C

n discs need exactly 2n − 1 moves: 1, 3, 7, 15… That number is the fingerprint of the recursion — each level doubles the work plus one move.

Your solution

main.cpp — your solution
Custom input for "Run my input"

Judging runs in your browser against hidden tests. A runaway loop is cut off after 3 seconds — still, make sure every loop has an exit. Your code is saved in this browser as you type.

Stuck? Hints

Hint 1 — Forget the small discs

To move n discs from A to C, you don't need to think about n discs. You need to think about one: the biggest one. It has to end up on C, and for that, C must be empty and the other n−1 discs must all be on B. That's the entire structure of the solution.

Hint 2 — Three lines, and one of them is a print

Move n−1 from from to aux (using to as spare). Print from->to. Move n−1 from aux to to (using from as spare). That's it. You never handle a disc directly — you only describe the situation and let the recursion do the work.

Hint 3 — The base case is n == 0, not n == 1

Both work, but n == 0 is cleaner: "moving zero discs" is a valid, complete, do-nothing request. With n == 1 as the base you have to special-case printing, and the three-step body stops being uniform. Choosing the base case well is half of writing a correct recursion.

Solution (try it first!) 
#include <iostream>
using namespace std;

void hanoi(int n, char from, char aux, char to) {
    if (n == 0) return;
    hanoi(n - 1, from, to, aux);
    cout << from << "->" << to << endl;
    hanoi(n - 1, aux, from, to);
}

int main() {
    int n;
    cin >> n;
    hanoi(n, 'A', 'B', 'C');
    return 0;
}

Look at how little code that was — six lines for a problem that takes most people a whiteboard to reason about. That's the payoff of recursion: you describe one layer, and the machine expands it into 2n − 1 moves. The cost is real though: the call stack grows to depth n, and if the recursion were linear instead of halving, large inputs would blow it. That's why every recursion needs a base case that is actually reachable. Last problem: one where the trick is arithmetic, not code — Trailing Zeros.

Deep dive

Why this works

To move n discs, think about only the largest one: it must land on C, so C must be empty and the other n−1 discs must be on B. The problem turns itself into two smaller copies of itself.

The cost

Exactly 2^n − 1 moves — the fingerprint of the recursion, where each level doubles the work plus one move. Call stack depth is n.

Where it goes wrong

  • Using n == 1 as the base case instead of n == 0 forces a special branch for printing and the three-step body stops being uniform.
  • Starting the second recursive call from from instead of aux produces duplicate and invalid moves — and it never errors, it is just wrong.

Next step

The last problem: the trick is arithmetic, not code — Trailing Zeros.

Two things to remember

  • Think only about the biggest disc; hand the rest to the recursion.
  • Base case n == 0 is what keeps the three steps uniform.
🐞 This version fails — open it and try

Second recursion starts from from instead of aux — moves duplicate

#include <iostream>
using namespace std;

void hanoi(int n, char from, char aux, char to) {
    if (n == 0) return;
    hanoi(n - 1, from, to, aux);
    cout << from << "->" << to << endl;
    hanoi(n - 1, from, aux, to);
}

int main() {
    int n;
    cin >> n;
    hanoi(n, 'A', 'B', 'C');
    return 0;
}