Tower of Hanoi Recursion — Stack Overflow from Frame Bloat

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 \times 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);
    }
}

Real-World Variations: From Puzzles to Production Patterns

Tower of Hanoi isn't just a teaching exercise — its recursive structure appears in real systems:

• Backup rotation schemes: Grandfather-father-son backup strategy maps exactly to the three-peg problem. The recursive rotation ensures every full backup cycle uses minimal tape swaps.
• MRI scan ordering: Some medical imaging sequences use a variant of Tower of Hanoi to order slice acquisitions, minimising mechanical movement of the gantry.
• Stack-based undo systems: The concept of moving a 'disc' from one stack to another while preserving order is used in multi-level undo/redo in editors like Vim and Photoshop.
• Disk defragmentation: Moving files on a fragmented disk to a temporary location before placing them contiguously is a direct analogy.

Understanding the pattern allows you to recognise it in unfamiliar domains. The key is always the self-similar substructure.

package io.thecodeforge.recursion;

import java.util.*;

/**
 * Grandfather-Father-Son backup rotation using Tower of Hanoi principle.
 * This assumes three backup media (daily, weekly, monthly) analogous to pegs A, B, C.
 */
public class BackupRotationScheduler {

    private static final List<String> backupLog = new ArrayList<>();
    private static int rotationDay = 0;

    public static void scheduleBackup(int n, String source, String dest, String aux) {
        if (n == 1) {
            rotationDay++;
            backupLog.add("Day " + rotationDay + ": Backup " + source + " -> " + dest);
            return;
        }
        scheduleBackup(n - 1, source, aux, dest);
        scheduleBackup(1, source, dest, aux);
        scheduleBackup(n - 1, aux, dest, source);
    }

    public static void main(String[] args) {
        // 3 levels: daily, weekly, monthly
        scheduleBackup(3, "Daily", "Monthly", "Weekly");
        backupLog.forEach(System.out::println);
    }
}