Tower of Hanoi Explained: Recursion, Logic & Real Code

public class TowerOfHanoi {

    /**
     * Moves 'discCount' discs from 'sourcePeg' to 'destinationPeg'
     * using 'auxiliaryPeg' as a temporary holding peg.
     *
     * @param discCount       number of discs to move
     * @param sourcePeg       the peg where the discs currently sit
     * @param destinationPeg  the peg where the discs need to end up
     * @param auxiliaryPeg    the spare peg used for temporary storage
     */
    public static void moveDiscs(
            int discCount,
            char sourcePeg,
            char destinationPeg,
            char auxiliaryPeg) {

        // BASE CASE: only one disc left — move it directly, no setup needed
        if (discCount == 1) {
            System.out.println(
                "Move disc 1 from peg " + sourcePeg + " to peg " + destinationPeg
            );
            return; // stop recursing — the problem is solved at this level
        }

        // STEP 1: Move the top (discCount - 1) discs out of the way
        // Destination becomes auxiliary so the big disc has room to land
        moveDiscs(discCount - 1, sourcePeg, auxiliaryPeg, destinationPeg);

        // STEP 2: Move the largest remaining disc to the destination
        // This is always a single, unobstructed move
        System.out.println(
            "Move disc " + discCount + " from peg " + sourcePeg + " to peg " + destinationPeg
        );

        // STEP 3: Move the (discCount - 1) discs from auxiliary onto destination
        // Source is now the auxiliary peg where we parked them in Step 1
        moveDiscs(discCount - 1, auxiliaryPeg, destinationPeg, sourcePeg);
    }

    public static void main(String[] args) {
        int numberOfDiscs = 3;

        System.out.println(
            "Solving Tower of Hanoi for " + numberOfDiscs + " discs:\n"
        );

        // Standard setup: Source = A, Destination = C, Auxiliary = B
        moveDiscs(numberOfDiscs, 'A', 'C', 'B');

        // Minimum moves formula: (2^n) - 1 = (2^3) - 1 = 7
        int minimumMoves = (int) Math.pow(2, numberOfDiscs) - 1;
        System.out.println("\nTotal moves taken: " + minimumMoves);
    }
}

public class TowerOfHanoiWithDepth {

    /**
     * Same algorithm as before, but with depth tracking added
     * so you can SEE the call stack building up and unwinding.
     */
    public static void moveDiscs(
            int discCount,
            char sourcePeg,
            char destinationPeg,
            char auxiliaryPeg,
            int callDepth) {

        // Indent output proportional to call depth — visualises stack depth
        String indent = "  ".repeat(callDepth);

        System.out.println(
            indent + "[Depth " + callDepth + "] moveDiscs(" +
            discCount + ", " + sourcePeg + " -> " + destinationPeg + ")"
        );

        if (discCount == 1) {
            // Base case: deepest point — stack starts unwinding from here
            System.out.println(
                indent + "  *** MOVE: disc 1 from " + sourcePeg + " to " + destinationPeg
            );
            return;
        }

        // Left branch: clear the way for the big disc
        moveDiscs(discCount - 1, sourcePeg, auxiliaryPeg, destinationPeg, callDepth + 1);

        // Mid-point action: place the big disc on the destination
        System.out.println(
            indent + "  *** MOVE: disc " + discCount +
            " from " + sourcePeg + " to " + destinationPeg
        );

        // Right branch: place the smaller discs on top of the big disc
        moveDiscs(discCount - 1, auxiliaryPeg, destinationPeg, sourcePeg, callDepth + 1);
    }

    public static void main(String[] args) {
        System.out.println("--- Call Stack Visualisation for N=3 ---\n");
        moveDiscs(3, 'A', 'C', 'B', 0);
    }
}

public class HanoiMoveCounter {

    // Counts moves recursively — matches the recurrence T(n) = 2*T(n-1) + 1
    public static long countMoves(int discCount) {
        if (discCount == 1) {
            return 1; // base case: one disc needs exactly one move
        }
        // Left branch moves + big disc move + right branch moves
        return 2 * countMoves(discCount - 1) + 1;
    }

    // Closed-form version: 2^n - 1 (much faster, same result)
    public static long countMovesFormula(int discCount) {
        return (long) Math.pow(2, discCount) - 1;
    }

    public static void main(String[] args) {
        System.out.printf("%-8s %-20s %-20s%n",
            "Discs", "Recursive Count", "Formula (2^n - 1)");
        System.out.println("-".repeat(50));

        // Show the exponential growth up to 20 discs
        for (int discCount = 1; discCount <= 20; discCount++) {
            long recursive = countMoves(discCount);
            long formula   = countMovesFormula(discCount);

            System.out.printf("%-8d %-20d %-20d%n",
                discCount, recursive, formula);
        }

        // Dramatic illustration of exponential scale
        System.out.println("\nFor 64 discs: " + countMovesFormula(64) + " moves");
        System.out.println("That's " + (countMovesFormula(64) / 31_557_600L) +
            " years at one move per second.");
    }
}

import java.util.ArrayList;
import java.util.List;

public class HanoiMoveRecorder {

    // Represents a single disc move — clean, testable, serialisable
    static class DiscMove {
        final int discNumber;
        final char fromPeg;
        final char toPeg;

        DiscMove(int discNumber, char fromPeg, char toPeg) {
            this.discNumber = discNumber;
            this.fromPeg    = fromPeg;
            this.toPeg      = toPeg;
        }

        @Override
        public String toString() {
            return "Disc " + discNumber + ": " + fromPeg + " -> " + toPeg;
        }
    }

    /**
     * Identical logic to the original — but instead of printing,
     * we append each move to a shared list that the caller owns.
     */
    public static void recordMoves(
            int discCount,
            char sourcePeg,
            char destinationPeg,
            char auxiliaryPeg,
            List<DiscMove> moveHistory) {

        if (discCount == 1) {
            // Base case: record the single move and return
            moveHistory.add(new DiscMove(discCount, sourcePeg, destinationPeg));
            return;
        }

        // Move smaller discs to auxiliary — record each step
        recordMoves(discCount - 1, sourcePeg, auxiliaryPeg, destinationPeg, moveHistory);

        // Record the big disc move
        moveHistory.add(new DiscMove(discCount, sourcePeg, destinationPeg));

        // Move smaller discs from auxiliary to destination — record each step
        recordMoves(discCount - 1, auxiliaryPeg, destinationPeg, sourcePeg, moveHistory);
    }

    public static void main(String[] args) {
        int numberOfDiscs = 3;
        List<DiscMove> moveHistory = new ArrayList<>();

        recordMoves(numberOfDiscs, 'A', 'C', 'B', moveHistory);

        System.out.println("Complete move history for " + numberOfDiscs + " discs:");
        System.out.println("Total moves: " + moveHistory.size() + "\n");

        // Now you can iterate, store to DB, send to a frontend, replay in a game, etc.
        for (int step = 0; step < moveHistory.size(); step++) {
            System.out.println("Step " + (step + 1) + ": " + moveHistory.get(step));
        }

        // Verify against the formula — they must always match
        long expectedMoves = (long) Math.pow(2, numberOfDiscs) - 1;
        boolean isOptimal  = moveHistory.size() == expectedMoves;
        System.out.println("\nSolution is optimal: " + isOptimal);
    }
}