Tower of Hanoi Explained: Recursion, Logic & Real Code

Most recursion tutorials give you factorial or Fibonacci and call it a day. Tower of Hanoi is different — it's the puzzle that makes recursion click. It's used in computer science courses worldwide not because it's academically cute, but because it perfectly mirrors how recursive thinking actually works: break a big problem into a smaller version of itself, trust the process, and let the call stack do the heavy lifting. It shows up in coding interviews at companies like Google, Amazon, and Meta — not because they want you to memorise it, but because solving it live reveals whether you can think recursively under pressure.

The problem has a deceptively simple rule set: three pegs, N discs stacked from largest to smallest on the first peg, and you need to move the whole stack to the last peg. You can only move one disc at a time, and a larger disc can never sit on top of a smaller one. An iterative solution to this problem is nightmarishly complex. A recursive solution is about eight lines of code. That contrast is the entire point — recursion isn't just a technique, it's the right tool for problems with self-similar structure.

By the end of this article you'll have a mental toolkit of those patterns: DFS vs BFS trade-offs, the two-pointer trick adapted for trees, the post-order 'gather-then-decide' approach, and more. Every problem below is chosen because it directly teaches a transferable pattern. Work through the code, tweak the inputs, break it — that's how the pattern becomes muscle memory.

Why Recursion Is the Only Sane Approach Here

Before writing a single line of code, let's understand why recursion is the natural fit and not just a clever trick.

The key insight is this: to move N discs from peg A to peg C, you must first move the top N-1 discs out of the way (to peg B), then slide the biggest disc to peg C, then move the N-1 discs from peg B onto peg C. That's it. That's the whole algorithm.

Notice that moving N-1 discs is exactly the same problem — just smaller. And moving N-2 discs is the same problem, even smaller. This self-similar structure is the definition of a recursively solvable problem. Every recursive call is trusting a slightly smaller version of itself to just work.

The base case is when N equals 1. You don't need to move anything out of the way — you just pick up the single disc and place it directly on the destination peg. That's your stopping condition. Without it, the function calls itself forever and your stack overflows.

package io.thecodeforge.recursion;

public class TowerOfHanoi {

    /**
     * io.thecodeforge: Standard recursive implementation of Tower of Hanoi.
     * Complexity: O(2^n)
     */
    public static void moveDiscs(
            int discCount,
            char sourcePeg,
            char destinationPeg,
            char auxiliaryPeg) {

        // BASE CASE: only one disc left — move it directly
        if (discCount == 1) {
            System.out.println("Move disc 1 from peg " + sourcePeg + " to peg " + destinationPeg);
            return;
        }

        // STEP 1: Move top (n-1) discs to auxiliary to free up the biggest disc
        moveDiscs(discCount - 1, sourcePeg, auxiliaryPeg, destinationPeg);

        // STEP 2: Move the largest remaining disc to destination
        System.out.println("Move disc " + discCount + " from peg " + sourcePeg + " to peg " + destinationPeg);

        // STEP 3: Move (n-1) discs from auxiliary to destination
        moveDiscs(discCount - 1, auxiliaryPeg, destinationPeg, sourcePeg);
    }

    public static void main(String[] args) {
        int n = 3;
        moveDiscs(n, 'A', 'C', 'B');
    }
}

Tracing the Call Stack: What Actually Happens Step by Step

Understanding the code is one thing. Understanding what the call stack looks like is what separates someone who memorised the solution from someone who truly gets recursion.

Let's trace N=3. The first call is moveDiscs(3, A, C, B). Before printing anything, it immediately calls moveDiscs(2, A, B, C). Before that prints anything, it calls moveDiscs(1, A, C, B) — which hits the base case and prints 'Move disc 1 from A to C'. Then control returns to the N=2 frame, which prints 'Move disc 2 from A to B', then calls moveDiscs(1, C, B, A), printing 'Move disc 1 from C to B'.

This is the critical mental model: recursive calls don't all run at once. Each frame is paused — frozen mid-execution — while it waits for a deeper call to return. The call stack is literally a stack of paused function frames. When a base case fires, the stack starts unwinding.

package io.thecodeforge.recursion;

public class TowerOfHanoiWithDepth {
    public static void moveWithTrace(int n, char s, char d, char a, int depth) {
        String indent = "  ".repeat(depth);
        if (n == 1) {
            System.out.println(indent + "[Base Case] Disc 1: " + s + " -> " + d);
            return;
        }
        
        System.out.println(indent + "Pushing frame N=" + n);
        moveWithTrace(n - 1, s, a, d, depth + 1);
        System.out.println(indent + "Current N=" + n + ": " + s + " -> " + d);
        moveWithTrace(n - 1, a, d, s, depth + 1);
    }
}

The Math Behind the Minimum Moves: Why 2ⁿ − 1?

Every correct solution to Tower of Hanoi with N discs takes exactly $2^n - 1$ moves. You can't do it in fewer. This isn't a fun fact — it's a provable consequence of the algorithm's structure.

Let's define $T(n)$ as the minimum number of moves needed for N discs. For $N=1$, that's 1 move. For any $N > 1$, the algorithm does $T(n-1)$ moves to shift the top stack to auxiliary, then 1 move for the big disc, then $T(n-1)$ moves again to shift the small stack onto the destination.

Formula: $T(n) = 2 imes T(n-1) + 1$. Unrolling this recurrence yields the geometric series result: $T(n) = 2^n - 1$.

package io.thecodeforge.recursion;

public class HanoiMath {
    public static long calculateMinMoves(int n) {
        // Use long to prevent overflow for N > 30
        return (long) Math.pow(2, n) - 1;
    }
    
    public static void main(String[] args) {
        System.out.println("Moves for 64 discs: " + calculateMinMoves(64));
    }
}

Storing Move History: A Practical Real-World Extension

Printing to the console is fine for learning, but in a real application — say, building a game, an animation engine, or a puzzle validator — you need to capture each move as structured data you can process, store, or replay. This transition uses the 'accumulator pattern,' threading a List through the recursive calls to collect results without breaking the functional purity of the logic.

package io.thecodeforge.recursion;

import java.util.*;

public class HanoiMoveRecorder {
    public record Move(int disc, char from, char to) {}

    public static void record(int n, char s, char d, char a, List<Move> history) {
        if (n == 1) {
            history.add(new Move(1, s, d));
            return;
        }
        record(n - 1, s, a, d, history);
        history.add(new Move(n, s, d));
        record(n - 1, a, d, s, history);
    }
}

Frequently Asked Questions