Towers of Hanoi: Recursive Algorithm With Code in C, C++, Java, Python and C#

On the machine used for this article, a C program generated all 1,073,741,823 moves for 30 disks in 4.6 seconds, and each extra disk roughly doubled the time. At that rate, the 64 disks of the puzzle’s legend would take about 2,500 years. At one move per second, they would take about 585 billion.

This guide explains the recursive Towers of Hanoi algorithm, proves why it needs exactly 2ⁿ − 1 moves, and implements it in C, C++, Java, Python and C#, followed by an iterative version that computes any move from the bits of its number. Every program was compiled and run for this article on Ubuntu 24.04 (x86-64): C with GCC 13.3 and Clang 18.1.3 under -std=c11 and -std=c17, C++ with g++ 13.3 and clang++ 18.1.3 under -std=c++17 and -std=c++20, all with -Wall -Wextra -pedantic and no warnings; Java on OpenJDK 21 with --release 17 -Xlint:all; Python 3.13 with ruff and mypy --strict clean; and C# on the .NET 10 SDK with analyzer warnings treated as errors. The five programs print byte-identical output, and every output block is captured verbatim. The code is in five GitHub repositories whose workflows run the tests on each commit, including MSVC, Windows and macOS jobs that were not run on the test machine.

What Is the Towers of Hanoi Problem?

The Towers of Hanoi is a puzzle with three pegs and n disks of different sizes, stacked on one peg from largest at the bottom to smallest at the top. The goal is to move the whole stack to another peg. Only one disk moves at a time, a move takes the top disk of a peg, and no disk may be placed on a smaller one. The minimum number of moves is 2ⁿ − 1.

The French mathematician Édouard Lucas published the puzzle in 1883. The story that came with it, of priests moving 64 golden disks and the world ending when they finish, is traced by the Wikipedia article on the Tower of Hanoi to the puzzle’s own instruction booklet rather than to an older tradition.

The puzzle survives in programming courses because its solution is the shortest useful example of a function that solves a problem by calling itself on a smaller copy of the same problem. The rest of this guide calls the three pegs A, B and C, numbers the disks from 1 (smallest) to n (largest), and moves the tower from A to C.

How the Recursive Solution Works

Look at the largest disk. It can move only when every other disk is out of the way, and the only place they can all be is the third peg. That observation is the whole algorithm. To move n disks from source to target:

1. Move the top n − 1 disks from source to spare, using target as the spare peg for that smaller job.
2. Move disk n from source to target. Both pegs are clear: source has nothing above disk n, and target is empty.
3. Move the n − 1 disks from spare to target, using source as the spare.

Steps 1 and 3 are the same problem with one disk fewer and the pegs relabelled. The recursion stops at zero disks, where there is nothing to do:

hanoi(n, source, target, spare):
    if n == 0:
        return                                  # no disks, nothing to move
    hanoi(n - 1, source, spare, target)         # step 1: clear the way
    move disk n from source to target           # step 2: the largest disk
    hanoi(n - 1, spare, target, source)         # step 3: restack on top of it

Every call works on one disk fewer than its caller, so a call with n disks reaches the base case after n levels. The deepest point of the recursion holds n + 1 calls at once, counting the call for zero disks.

Worked Example: Three Disks

This is the output of every program in this guide for three disks, moving the tower from A to C:

Output:

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
3 disks: 7 moves

Moves 1 to 3 are step 1: the call hanoi(2, A, B, C) moves disks 1 and 2 to B. Move 4 is step 2, the only move disk 3 ever makes. Moves 5 to 7 are step 3, hanoi(2, B, C, A), which carries the same two disks from B to C.

Read the disk column on its own: 1, 2, 1, 3, 1, 2, 1. Disk 1 moves on every odd-numbered move, disk 2 on moves 2, 6, 10 and every fourth move after that, and disk k first moves on move 2ᵏ⁻¹. That pattern is what the iterative solution later in this guide uses to compute any move without the ones before it.

Why the Towers of Hanoi Needs 2ⁿ − 1 Moves

Let T(n) be the number of moves the recursive solution makes for n disks. Steps 1 and 3 each cost T(n − 1), and step 2 costs one move:

T(0) = 0
T(n) = 2·T(n − 1) + 1

Unrolling it gives 1, 3, 7, 15, 31, …, which is T(n) = 2ⁿ − 1. Substituting confirms it: 2·(2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 1.

No solution can do better. Disk n has to move at least once. Before its first move, the other n − 1 disks must all sit on the third peg, which takes at least T(n − 1) moves from the starting position. After its last move, they must all end up on top of it, which takes at least T(n − 1) more. So any solution needs at least 2·T(n − 1) + 1 moves, the recursive solution makes exactly that many, and by induction 2ⁿ − 1 is the minimum.

The count for 64 disks is the largest value a 64-bit unsigned integer can hold. That coincidence matters for the code: a uint64_t, ulong or unsigned long long holds every count up to 64 disks, a signed 64-bit long stops at 63, and computing the count with a shift goes wrong earlier still, as one of the mistakes below shows.

Measured: Each Extra Disk Roughly Doubles the Running Time

How This Was Measured

The timings come from one machine and one run of the program. No CPU pinning or frequency-scaling control was applied, and no percentiles were captured. The volatile counter is there so the compiler cannot replace the loop with the closed-form count, and the solver lives in a separate source file so the callback is not inlined away.

Output:

 n          moves  recursive s  ns/move  iterative s  ns/move
20        1048575        0.004     4.20        0.008     7.53
21        2097151        0.009     4.13        0.016     7.44
22        4194303        0.017     4.05        0.031     7.49
23        8388607        0.045     5.34        0.061     7.25
24       16777215        0.067     4.02        0.124     7.41
25       33554431        0.137     4.09        0.266     7.92
26       67108863        0.279     4.16        0.483     7.20
27      134217727        0.552     4.11        1.012     7.54
28      268435455        1.146     4.27        2.093     7.80
29      536870911        2.309     4.30        4.222     7.86
30     1073741823        4.557     4.24        8.137     7.58

The cost per move stayed between 4.0 and 4.3 ns for the recursive solver, apart from one outlier at 23 disks, so the total time doubled with each disk: 0.55 s at 27 disks, 1.15 s at 28, 2.31 s at 29 and 4.56 s at 30. That is what O(2ⁿ) looks like on a real machine.

The opening figure is an extrapolation from this table, not a measurement: 2⁶⁴ − 1 moves at 4.24 ns each is about 7.8 × 10¹⁰ seconds, or roughly 2,500 years. It covers generating the moves, not printing them. Printing is far slower: the command-line program in the C repository, built with the same flags, wrote the 1,048,575 moves for 20 disks to /dev/null in 0.088 to 0.118 s over five runs, about 85 ns per move, or roughly 20 times the cost of generating one. Those five runs were timed from the shell, including process start-up.

The iterative solver was slower on this machine, at 7.2 to 7.9 ns per move. Each of its moves counts trailing zero bits in a loop and takes two remainders by 3, while the recursive solver’s cost per move is spread over calls that each do very little. That explanation is reasoning from the code, not a profile.

Towers of Hanoi in C, C++, Java, Python and C#

All five programs below are complete. Each defines hanoi(n, source, target, spare) with the parameters in the same order, prints every move, returns the number of moves, and prints the three-disk output shown in the worked example.

Towers of Hanoi in C

/* towers_of_hanoi.c - the recursive Towers of Hanoi solution in C11.
 * Build: gcc -std=c11 -Wall -Wextra -pedantic towers_of_hanoi.c -o towers_of_hanoi
 */
#include <stdio.h>

/* Moves n disks from peg `source` to peg `target`, using `spare` as the
 * third peg, prints each move, and returns the number of moves made. */
static unsigned long long hanoi(unsigned n, char source, char target, char spare)
{
    if (n == 0)
        return 0;                                    /* nothing to move */

    unsigned long long moves = hanoi(n - 1, source, spare, target);
    printf("Move disk %u from %c to %c\n", n, source, target);
    moves += 1;
    moves += hanoi(n - 1, spare, target, source);
    return moves;
}

int main(void)
{
    const unsigned n = 3;
    unsigned long long moves = hanoi(n, 'A', 'C', 'B');
    printf("%u disks: %llu moves\n", n, moves);
    return 0;
}

n is unsigned, so a negative disk count cannot reach the function, and the base case is n == 0. The move count is unsigned long long, which C guarantees to be at least 64 bits wide, so it holds 2ⁿ − 1 for every n up to 64. Compile and run it with:

gcc -std=c11 -Wall -Wextra -pedantic towers_of_hanoi.c -o towers_of_hanoi
./towers_of_hanoi

Towers of Hanoi in C++

// towers_of_hanoi.cpp - the recursive Towers of Hanoi solution in C++17.
// Build: g++ -std=c++17 -Wall -Wextra -pedantic towers_of_hanoi.cpp -o towers_of_hanoi
#include <cstdint>
#include <iostream>

// Moves n disks from source to target, using spare as the third peg,
// prints each move, and returns the number of moves made.
std::uint64_t hanoi(int n, char source, char target, char spare)
{
    if (n <= 0)
        return 0;                                    // nothing to move

    std::uint64_t moves = hanoi(n - 1, source, spare, target);
    std::cout << "Move disk " << n << " from " << source << " to " << target << '\n';
    ++moves;
    moves += hanoi(n - 1, spare, target, source);
    return moves;
}

int main()
{
    const int n = 3;
    const std::uint64_t moves = hanoi(n, 'A', 'C', 'B');
    std::cout << n << " disks: " << moves << " moves\n";
}

The C++ version takes an int and treats any count of zero or less as nothing to move. main stores the result before printing the total, and that is not a style choice: writing the call inside the same std::cout statement as the total prints the moves in the wrong place, as the fourth mistake below shows. The repository’s hanoi.hpp generalises this into a template that hands each move to a callback, so the same solver can print, record or count.

Towers of Hanoi in Java

// TowersOfHanoi.java - the recursive Towers of Hanoi solution in Java 17.
// Compile: javac TowersOfHanoi.java   Run: java TowersOfHanoi
public class TowersOfHanoi {

    /** Moves n disks from source to target, using spare as the third peg,
     *  prints each move, and returns the number of moves made. */
    static long hanoi(int n, char source, char target, char spare) {
        if (n <= 0) {
            return 0;                                   // nothing to move
        }
        long moves = hanoi(n - 1, source, spare, target);
        System.out.println("Move disk " + n + " from " + source + " to " + target);
        moves++;
        moves += hanoi(n - 1, spare, target, source);
        return moves;
    }

    public static void main(String[] args) {
        int n = 3;
        long moves = hanoi(n, 'A', 'C', 'B');
        System.out.println(n + " disks: " + moves + " moves");
    }
}

A Java long holds up to 2⁶³ − 1, so this listing’s count is correct up to 63 disks. The repository’s Hanoi.moveCount() returns a BigInteger for an exact count at any size, and Hanoi.solve() passes each move to a Consumer<Move> instead of printing it.

The Java repository also contains HanoiAnimation.java, a Swing animation of the same recursive solution built on a JPanel and a javax.swing.Timer, so every repaint runs on the event dispatch thread. Run it with java HanoiAnimation 5, or write a frame to a PNG without a display with java HanoiAnimation 5 --snapshot frame.png 12. If you find an older Towers of Hanoi applet, note that it will not compile on current Java: JEP 504 removed the Applet API, including javax.swing.JApplet, in JDK 26.

Towers of Hanoi in Python

"""The recursive Towers of Hanoi solution in Python 3.

Run:  python3 towers_of_hanoi.py
"""


def hanoi(n: int, source: str, target: str, spare: str) -> int:
    """Move n disks from source to target, using spare as the third peg.

    Prints each move and returns the number of moves made.
    """
    if n <= 0:
        return 0                                    # nothing to move
    moves = hanoi(n - 1, source, spare, target)
    print(f"Move disk {n} from {source} to {target}")
    moves += 1
    moves += hanoi(n - 1, spare, target, source)
    return moves


if __name__ == "__main__":
    n = 3
    moves = hanoi(n, "A", "C", "B")
    print(f"{n} disks: {moves} moves")

Python integers do not overflow, so the count is exact for any n. Python’s default recursion limit is 1,000 frames, and this function needs only n + 1 of them. The limit would allow several hundred disks, and 2ⁿ − 1 moves rules that out long before the stack does. The repository’s hanoi.py rewrites the solver as a generator, solve(), that yields Move tuples instead of printing.

Towers of Hanoi in C#

// Program.cs - the recursive Towers of Hanoi solution in C#.
// Run: dotnet run
using System;

namespace MyCPlus.Recursion;

public static class TowersOfHanoi
{
    // Moves n disks from source to target, using spare as the third peg,
    // prints each move, and returns the number of moves made.
    public static ulong Hanoi(int n, char source, char target, char spare)
    {
        if (n <= 0)
            return 0;                                   // nothing to move

        ulong moves = Hanoi(n - 1, source, spare, target);
        Console.WriteLine($"Move disk {n} from {source} to {target}");
        moves++;
        moves += Hanoi(n - 1, spare, target, source);
        return moves;
    }

    public static void Main()
    {
        const int n = 3;
        ulong moves = Hanoi(n, 'A', 'C', 'B');
        Console.WriteLine($"{n} disks: {moves} moves");
    }
}

ulong holds 2⁶⁴ − 1, so the count is exact up to 64 disks. The file builds as a console project (dotnet new console, then replace Program.cs). The repository’s HanoiSolver class adds an Action<Move> callback, an iterative solver and a BigInteger move count.

Solving the Towers of Hanoi Without Recursion

The disk sequence 1, 2, 1, 3, 1, 2, 1 is the number of times each move number can be divided by 2, plus one. Move k moves disk 1 + (number of trailing zero bits in k). The pegs follow from the bits of k too. With the pegs numbered 0, 1 and 2, move k goes from peg (k & (k − 1)) mod 3 to peg ((k | (k − 1)) + 1) mod 3. That formula moves the tower from peg 0 to peg 2 when n is odd and to peg 1 when n is even, so the program swaps the labels of the target and spare pegs for even n.

/* towers_of_hanoi_iterative.c - Towers of Hanoi without recursion, in C11.
 * Move k is computed from the bits of k alone.
 * Build: gcc -std=c11 -Wall -Wextra -pedantic towers_of_hanoi_iterative.c -o hanoi_iter
 */
#include <stdint.h>
#include <stdio.h>

/* Prints the 2^n - 1 moves for n disks (1 <= n <= 63) and returns the count. */
static uint64_t hanoi_iterative(unsigned n, char source, char target, char spare)
{
    /* The formula below moves the tower from index 0 to index 2 when n is
     * odd and to index 1 when n is even. */
    const char peg[3] = { source,
                          n % 2 == 1 ? spare : target,
                          n % 2 == 1 ? target : spare };
    const uint64_t last = (UINT64_C(1) << n) - 1;

    for (uint64_t k = 1; k <= last; ++k) {
        unsigned disk = 1;                     /* 1 + trailing zero bits of k */
        for (uint64_t t = k; (t & 1u) == 0; t >>= 1)
            ++disk;
        char from = peg[(k & (k - 1)) % 3];
        char to = peg[((k | (k - 1)) % 3 + 1) % 3];
        printf("Move disk %u from %c to %c\n", disk, from, to);
    }
    return last;
}

int main(void)
{
    const unsigned n = 3;
    uint64_t moves = hanoi_iterative(n, 'A', 'C', 'B');
    printf("%u disks: %llu moves\n", n, (unsigned long long)moves);
    return 0;
}

It prints exactly the same seven moves as the recursive program. The test suites go further: the recursive and iterative solvers produce identical sequences for every n from 0 to 20 in C and C++ (0 to 18 in Java and C#, 0 to 15 in Python), and every move of every sequence passes a simulator that rejects any move of a disk that is not on top or that lands on a smaller disk.

Because move k depends only on k, you can jump straight to any move. Move 9,223,372,036,854,775,808 of the 64-disk puzzle, halfway through, is the single move of disk 64 from A to C. Generating the moves before it, at the measured rate, would take about 1,240 years.

The textbook formula breaks at 64 disks

The program above computes the destination as ((k | (k - 1)) % 3 + 1) % 3 rather than ((k | (k - 1)) + 1) % 3. The two agree in Python, where integers do not overflow. They do not agree in 64-bit unsigned arithmetic, where k | (k - 1) can be 2⁶⁴ − 1 and adding 1 wraps it to 0. That happens for exactly 64 moves of the 64-disk solution, those with k = 2⁶⁴ − 2ʲ, and one of them is the largest disk’s only move. The C test suite compares the formula against an independent reference that walks down the recursion, and with the textbook form it reported:

k=9223372036854775808: reference 64 A->C, got 64 A->A

That is disk 64 moved from A to A. Reducing modulo 3 before adding 1 cannot overflow, and the same test passes for all 2,000 moves it samples, including all 64 of those. The listing above is limited to 63 disks by its shift, so it never meets the case; the repositories’ move_at functions accept 64 disks, and their tests check this boundary in C, C++, Java and C#.

Four Towers of Hanoi Mistakes That Pass a Quick Test

Each of these programs prints a sensible answer for the three-disk case a first test usually tries.

1. A Base Case of n == 1

Stopping the recursion at one disk is a common way to write it, and it works for every n from 1 upward. For zero disks it never stops: hanoi(0) calls hanoi(-1), which calls hanoi(-2), until the stack runs out.

/* base_case_one.c - DO NOT COPY. The base case is n == 1, so n == 0 never
 * reaches it: the recursion counts down through -1, -2, ... until the
 * stack runs out. */
#include <stdio.h>
#include <stdlib.h>

static long long moves;

static void hanoi(int n, char source, char target, char spare)
{
    if (n == 1) {
        ++moves;                      /* move the one remaining disk */
        return;
    }
    hanoi(n - 1, source, spare, target);
    ++moves;
    hanoi(n - 1, spare, target, source);
}

int main(int argc, char **argv)
{
    int n = argc > 1 ? atoi(argv[1]) : 0;
    printf("solving for %d disks\n", n);
    fflush(stdout);
    hanoi(n, 'A', 'C', 'B');
    printf("%d disks: %lld moves\n", n, moves);
    return 0;
}

Run with 3, it prints 3 disks: 7 moves. Run with 0, each language failed in its own way:

Java and Python raise exceptions a caller can catch. .NET does not let a program catch a stack overflow, so the C# process ends. With a base case of n == 0, every implementation in this guide returns zero moves for zero disks.

2. Passing the Pegs in the Same Order

The first recursive call has to send the smaller disks to the spare peg. Copying the outer call’s argument order sends them to the target instead:

/* copied_arguments.c - DO NOT COPY. The first recursive call passes the pegs
 * in the same order as the outer call, so the n - 1 smaller disks go to the
 * target instead of the spare. The move count is still 2^n - 1; the moves
 * are illegal. A simulator below checks each one. */
#include <stdio.h>

static int peg[3][8], height[3];
static long moves;
static long first_illegal;           /* 0 while every move has been legal */

static void move(int disk, char source, char target)
{
    int f = source - 'A', t = target - 'A';
    ++moves;
    if (first_illegal != 0)
        return;
    if (height[f] == 0 || peg[f][height[f] - 1] != disk ||
        (height[t] > 0 && peg[t][height[t] - 1] < disk)) {
        first_illegal = moves;
        printf("move %ld is illegal: disk %d from %c to %c", moves, disk,
               source, target);
        if (height[t] > 0)
            printf(" lands on disk %d", peg[t][height[t] - 1]);
        printf("\n");
        return;
    }
    peg[t][height[t]++] = peg[f][--height[f]];
}

static void hanoi(int n, char source, char target, char spare)
{
    if (n == 0)
        return;
    hanoi(n - 1, source, target, spare);     /* BUG: should be source, spare, target */
    move(n, source, target);
    hanoi(n - 1, spare, target, source);
}

int main(void)
{
    const int n = 3;
    for (int i = 0; i < n; ++i)
        peg[0][i] = n - i;
    height[0] = n;
    hanoi(n, 'A', 'C', 'B');
    printf("%d disks: %ld moves (2^n - 1 = %d)\n", n, moves, (1 << n) - 1);
    printf("solved: %s\n", first_illegal == 0 && height[2] == n ? "yes" : "no");
    return 0;
}

Output:

move 2 is illegal: disk 2 from A to C lands on disk 1
3 disks: 7 moves (2^n - 1 = 7)
solved: no

The program still makes 2ⁿ − 1 moves, so a test that checks only the count passes. The second move puts disk 2 on disk 1. The tests in the repositories therefore replay every move on a simulated set of pegs and check the final position, rather than counting.

3. Computing 2ⁿ − 1 With a Shift

(1 << n) - 1 is the obvious way to compute the move count, and with a 32-bit int it is both well defined and correct only up to 30 disks:

/* shift_overflow.c - DO NOT COPY. 2^n - 1 computed as (1 << n) - 1 in int.
 * For n >= 31 the shift is undefined behaviour in C. */
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv)
{
    for (int i = 1; i < argc; ++i) {
        int n = atoi(argv[i]);
        int moves = (1 << n) - 1;
        printf("%d disks: %d moves\n", n, moves);
    }
    return 0;
}

In C, shifting a 32-bit int by 31 or more places is undefined behaviour. With UndefinedBehaviorSanitizer, the 32-disk run reported:

pitfalls/shift_overflow.c:10:24: runtime error: shift exponent 32 is too large for 32-bit type 'int'

For 31 disks the C program printed the correct 2,147,483,647, although the sanitizer reported both the shift (left shift of 1 by 31 places cannot be represented in type 'int') and the subtraction that follows it. A result that is right by accident on one compiler is the kind of undefined behaviour that survives testing. Java and C# define the result instead: they use only the low five bits of the shift count for an int and the low six for a long, so 1 << 32 is 1 and 1L << 64 is 1, and the move count comes out as 0 with no error. The Java and C# programs are in the repositories’ pitfalls directories.

Use a type that holds the answer, and treat 64 disks as a special case if the type is 64 bits wide, because shifting a 64-bit value by 64 is undefined in C and C++ too. The repositories’ hanoi_move_count and move_count functions do exactly that, and the Java and C# versions return a BigInteger.

4. Printing the Moves and the Total in One C++ Statement

This version of main calls hanoi() inside the statement that prints the total:

// print_in_one_statement.cpp - DO NOT COPY. hanoi() prints the moves, and
// main() calls it in the middle of the statement that prints the total.
// Since C++17 the operands of << are evaluated left to right, so
// "3 disks: " is written before hanoi() runs and prints the moves.
#include <cstdint>
#include <iostream>

std::uint64_t hanoi(int n, char source, char target, char spare)
{
    if (n <= 0)
        return 0;
    std::uint64_t moves = hanoi(n - 1, source, spare, target);
    std::cout << "Move disk " << n << " from " << source << " to " << target << '\n';
    ++moves;
    moves += hanoi(n - 1, spare, target, source);
    return moves;
}

int main()
{
    const int n = 3;
    std::cout << n << " disks: " << hanoi(n, 'A', 'C', 'B') << " moves\n";
}

Output:

3 disks: Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
7 moves

Since C++17, the operands of << are evaluated left to right, so "3 disks: " reaches the stream before hanoi() runs and prints its moves. Before C++17 the order was unspecified; g++ 13.3 and clang++ 18.1.3 produced the same output under -std=c++14. The equivalent one-line statement printed correctly in C, Java, Python and C#, because each of them evaluates the call before anything is written: printf receives its arguments only after they are evaluated, and Java’s +, Python’s f-string and C#’s interpolated string build the whole line first. Store the result, then print it.

Time and Space Complexity of the Towers of Hanoi

No algorithm can beat O(2ⁿ) time when the output is the list of moves, because the list itself has 2ⁿ − 1 entries. For this algorithm the stack is not the constraint. The recursion is n + 1 calls deep, and each call’s frame lives on the call stack for as long as its subproblem runs. Compare quicksort, whose recursion can grow to one level per element on sorted input: Hanoi’s depth grows with the number of disks, and the running time becomes impractical first.

The recursion solves the same smaller problem twice with different peg labels, but caching does not help. Memoization pays off when identical subproblems produce reusable results, as in the knapsack problem. Here every subproblem has to emit its own moves, and the output alone is exponential. The structure is closer to merge sort: split the job into two half-sized recursive calls with a small piece of work between them.

Where the Towers of Hanoi Shows Up

• Teaching recursion and induction. The solution, its move count and the proof that the count is minimal all follow the same structure, which is why the puzzle appears in introductory programming and discrete mathematics courses.
• Binary counting and Gray codes. The disk moved on move k is set by the trailing zero bits of k, and the bit that changes between consecutive Gray codes identifies the disk to move.
• Backup rotation. The “Tower of Hanoi” backup scheme reuses backup media on the same pattern as the disks: one set every other day, the next every fourth day, and so on.
• Psychology research. Problem-solving and executive-function studies use the puzzle and related tasks such as the Tower of London.

Key Takeaways

• The recursion has three steps: move n − 1 disks to the spare peg, move the largest disk, move the n − 1 disks back on top of it.
• The minimum is 2ⁿ − 1 moves, proved by the same argument that builds the algorithm. For 64 disks that is 18,446,744,073,709,551,615.
• Each extra disk doubles the work. Measured in C: 4.56 s for 30 disks at about 4.2 ns per move, which extrapolates to roughly 2,500 years for 64.
• Use n == 0 as the base case. A base case of n == 1 recursed until the stack overflowed for zero disks in all four languages tried.
• Check moves, not counts. A solver with its peg arguments in the wrong order still makes 2ⁿ − 1 moves; a count check passes it and a move-by-move simulation catches it.
• Do not compute 2ⁿ − 1 with 1 << n in an int. Java and C# returned 0 for 32 disks; in C it is undefined behaviour.
• Any move can be computed directly from its number, but in 64-bit arithmetic the commonly quoted peg formula wraps for 64 disks.

Frequently Asked Questions

Conclusion

The Towers of Hanoi is three lines of recursion and an exponential amount of work, and both halves of that sentence are worth understanding. The recursion shows how a problem can be solved entirely in terms of a smaller copy of itself. The 2ⁿ − 1 moves show why a correct algorithm can still be unusable, and the doubling column in the timing table makes that concrete in a way the formula alone does not.

The mistakes are as instructive as the solution. A base case at one disk, arguments in the wrong order, a shift in the wrong integer type, or an output statement in the wrong place each produce a plausible answer for three disks. The tests in the repositories catch them by simulating every move and checking the boundaries at 0, 63 and 64 disks, and the same habit carries over to the other recursive problems in the algorithms section.

Source Code and Tests

All the code on this page, with its tests, is in one directory per language:

Language	Repository directory	Build
C	mycplus/c-examples › recursion/towers-of-hanoi
C++	mycplus/cpp-examples › recursion/towers-of-hanoi
Java	mycplus/java-examples › recursion/towers-of-hanoi
Python	mycplus/python-examples › recursion/towers-of-hanoi
C#	mycplus/csharp-examples › recursion/towers-of-hanoi

The C and C++ examples build with CMake:

cmake -S . -B build
cmake --build build
ctest --test-dir build --output-on-failure

Java runs with javac --release 17 -Xlint:all -Werror -d build src/*.java tests/*.java pitfalls/*.java followed by java -ea -cp build HanoiTest; Python with python3 -m unittest discover -s tests -v; C# with dotnet build TowersOfHanoi.slnx -c Release followed by dotnet run --project tests/TowersOfHanoiTests -c Release --no-build.

What a green badge means, exactly:

• C: compiles with GCC and Clang under C11 and C17 and with MSVC /W4 /WX, warnings as errors; the recursive and iterative solvers produce identical, legal, complete move sequences for 0 to 20 disks; hanoi_move_at agrees with an independent reference on 2,000 moves of the 64-disk puzzle; the move count is checked at 63, 64 and 65 disks; the command-line program rejects malformed input; the tests run clean under AddressSanitizer and UndefinedBehaviorSanitizer; both listings print the output above byte for byte; and the base-case and shift pitfalls fail the way this page says.
• C++: g++ and clang++ under C++17 and C++20 and MSVC /W4 /WX /permissive-, warnings as errors; the same solver, 64-disk, boundary and input checks as C, under AddressSanitizer and UndefinedBehaviorSanitizer too; the listing’s output; and the output of the one-statement pitfall.
• Java: Temurin 17, 21 and 25 on Linux and Windows; the same solver checks for 0 to 18 disks and 2,000 moves of the 64-disk puzzle; the listing’s output; the animation’s model solving six disks and rendering a frame without a display; and the shift and base-case pitfalls.
• Python: 3.10 to 3.14 on Linux and Windows; ruff and mypy --strict; the solver checks for 0 to 15 disks and move_at against the reference for 64, 65 and 100 disks; input validation; the listing’s output; and the RecursionError pitfall.
• C#: .NET 10 on Linux, Windows and macOS with analyzer warnings as errors; the same solver checks as Java; the listing’s output; and the shift and stack-overflow pitfalls.

The builds do not check the timing table, which came from one machine and would differ on another.