Tower of Hanoi in C: Solve the Puzzle

The Tower of Hanoi puzzle asks you to move a stack of disks between three pegs without placing a larger disk on a smaller one. A C program can print the legal move sequence, one disk at a time.

In this piece, I’ll explain how the recursive calls use the peg arguments and show the program’s output for three disks.

TL;DR

Move the top n−1 disks to the helper peg, move the largest disk to the destination, then move those n−1 disks onto it. The C function below follows that sequence and prints 2^n − 1 moves.

  • Call hanoi(n, source, helper, destination).
  • Stop when n is zero.
  • For three disks, the program prints seven legal moves.

What Is the Tower of Hanoi Algorithm?

Tower of Hanoi is a puzzle where a stack of different-sized disks moves between three pegs. Move one top disk at a time, and never place a larger disk on a smaller one.

The recursive algorithm treats the largest disk as the key to each subproblem. To move a stack of n disks, first clear the n−1 disks above the largest one onto the helper peg. Move the largest disk once, then transfer the smaller stack from the helper peg to the destination.

Recursion means a function calls itself with a smaller version of its original task, while the same three physical pegs take new roles in each hanoi call. Argument positions decide where every disk goes, so I keep source, helper and destination in that order because each call can be checked against those roles. The peg holding the smaller stack becomes the source, the previously empty peg becomes the helper, and the final peg remains the destination.

The stop condition is n == 0, which requires no action. When a call reaches zero, it returns so its caller can continue. For one disk, the smaller-stack calls return and the function prints one move.

Let M(n) count moves for n disks, with M(0) = 0. Each call solves two stacks of n−1 disks and moves the largest disk once, so M(n) = 2M(n−1) + 1. Expanding this recurrence gives M(n) = 2^n − 1.

PartActionReason
First callMove n−1 disks to helperClear the largest disk
Middle moveMove disk n to destinationAll smaller disks are out of its way
Second callMove n−1 disks to destinationComplete the stack transfer

For a three-disk stack, its smaller disks take three moves to clear. Disk three then moves once, and the final transfer takes three more. The total is seven, which agrees with 2^3 − 1.

The three parts of the recurrence match physical actions, not merely lines of code. The first subproblem frees the largest disk, the middle action moves that disk exactly once, and the second subproblem puts every smaller disk above it. The same reasoning applies to a single disk when the smaller-stack calls reach zero.

The recursive calls do not copy or store disks in arrays. They describe the move plan using the count and peg labels. Since every printed line is one disk movement, counting those lines gives a direct way to check whether the program’s result matches the formula.

For a call with n disks, the first recursive call moves n−1 disks from the same source to the helper. The middle statement moves disk n, which is the largest disk in that subproblem. The final call transfers the waiting disks to the destination, preserving their order throughout.

How to Solve Tower of Hanoi in C Step by Step

The implementation uses characters for peg names and an integer for the number of disks still in the current subproblem. I kept the recursive function focused on one job: print the legal move sequence for the requested stack.

Step 1: Assign the three peg roles

The function signature is hanoi(disks, source, helper, destination). The first argument says how many disks to move, and the remaining arguments label the roles in this call. Starting with A as source, B as helper and C as destination gives a consistent move direction.

Those role names describe the current subproblem, not permanent identities. In the first recursive call, destination becomes the helper because the smaller disks must move out of the way. In the second call, the old helper becomes the source for moving those disks onto the largest disk.

Step 2: Make the smaller calls around one move

The function first transfers disks − 1 from source to helper, using destination temporarily. It then prints the move of disk n from source to destination. Finally, it transfers the smaller stack from helper to destination, using the old source as helper.

static void hanoi(unsigned int disks, char source, char helper, char destination)
{
    if (disks == 0) {
        return;
    }

    hanoi(disks - 1, source, destination, helper);
    printf("Move disk %u from %c to %c\n", disks, source, destination);
    ++move_count;
    hanoi(disks - 1, helper, source, destination);
}

When disks is zero, the return prevents another call from decreasing it. Otherwise, the first call finishes before the middle move is printed. The second call then finishes the transfer, so the output order follows the legal sequence rather than listing all recursive calls first.

Step 3: Compile the complete program and run it

The full file checks its input before casting the count to unsigned. I compiled it with GCC in C17 mode and warnings enabled, then supplied three disks. The allowed range is 1 through 10 because each extra disk nearly doubles the number of printed lines.

#include <stdio.h>

static unsigned long long move_count = 0;

static void hanoi(unsigned int disks, char source, char helper, char destination)
{
    if (disks == 0) {
        return;
    }

    hanoi(disks - 1, source, destination, helper);
    printf("Move disk %u from %c to %c\n", disks, source, destination);
    ++move_count;
    hanoi(disks - 1, helper, source, destination);
}

int main(void)
{
    int disks;

    printf("Number of disks (1-10): ");
    if (scanf("%d", &disks) != 1 || disks < 1 || disks > 10) {
        fprintf(stderr, "Enter a whole number from 1 to 10.\n");
        return 1;
    }

    hanoi((unsigned int)disks, 'A', 'B', 'C');
    printf("Total moves: %llu\n", move_count);
    return 0;
}

Save the program as tower_hanoi.c. Build and run it with these commands, then enter 3 when prompted.

gcc -std=c17 -Wall -Wextra -Wpedantic tower_hanoi.c -o tower_hanoi
./tower_hanoi

I ran the compiled file with three disks. The terminal returned this exact sequence:

Number of disks (1-10): 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
Total moves: 7
Terminal output showing seven Tower of Hanoi moves for three disks
The program prints the seven moves needed for three disks.

The output starts by moving disk one from A to C, then moves disk two to B. The final printed move sends disk one from A to C, leaving all three disks on C in size order. The counter agrees with the recurrence: 2^3 − 1 equals 7.

Step 4: Trace a call without losing the peg names

With three disks, the first call is hanoi(3, A, B, C). Its first child is hanoi(2, A, C, B), so that subproblem moves the two smaller disks from A to B. After it returns, the parent prints disk three from A to C.

The parent’s second child is hanoi(2, B, A, C). It transfers the stack from B to C. The value 2 becomes 1 and then 0 as the calls descend, which is why the process ends instead of recursing indefinitely.

Each stack frame pauses at the first recursive call. It resumes to print one move, then pauses again at the second call. Reading the output in that order is a practical way to follow the call stack: the deepest call prints first, and its caller continues afterward.

Edge Cases and Move Counts

The input check accepts whole-number counts from 1 to 10. It rejects missing or nonnumeric input, and it rejects values outside that range before recursion begins.

InputResult
1One move from A to C
0 or a negative numberRejected before recursion
Text or missing valueRejected when scanf does not read an integer
Above 10Rejected to limit printed output

That limit is for the program’s printed demonstration, not a mathematical limit on the puzzle. At ten disks, the program would print 1,023 lines. Increasing the bound also increases output exponentially and uses one active call frame per disk.

The time complexity is O(2^n), because the program prints exactly 2^n − 1 moves. The recursive call stack uses O(n) space, since each level reduces the disk count by one before reaching the base case. The counter uses unsigned long long here, while the input bound keeps both output volume and arithmetic modest.

DisksMinimum moves
11
23
37
415
101,023

The table gives quick checks for runs with different disk counts. A two-disk stack requires three moves, while four disks require fifteen. Each added disk doubles the previous count and adds one, so adjacent rows test the recurrence.

Compare the printed total after the program finishes, rather than estimating from the number of visible line breaks. The counter counts one movement at the point where the largest disk in the active subproblem moves. This makes it useful for spotting whether the output and the recursive call structure agree.

These two costs describe different resources. The move count measures work printed to the terminal, while the stack measures unfinished calls held in memory at the same time. At each level the function makes two smaller calls, but those calls run in sequence rather than remaining active together.

That distinction explains why stack use grows linearly while output grows exponentially. A large disk count can therefore make the output impractical long before the code itself becomes difficult to read. For this example, keeping the bound at ten makes the entire sequence inspectable.

If the moves seem reversed, check the initial call before changing the recursive statements. The order hanoi(disks, ‘A’, ‘B’, ‘C’) means transfer from A to C with B as helper. Switching the second and third labels changes the destination, but does not change the move count.

A zero-disk base case is convenient because it lets the same function handle every smaller subproblem. An alternative base case at one disk can work too, but it needs a separate direct move and consistent role ordering. This version uses zero to make the return rule explicit.

The input check also distinguishes a numeric value from readable text. scanf returns the number of fields it converted, so a return other than 1 means it did not read one integer. The range checks then reject values that would create no useful move sequence or produce a long demonstration.

The recursive stack grows with n because each call waits for a smaller call to finish. For very large values, both the output size and call depth become practical limits before the formula itself becomes difficult to state. This example keeps its input range small and explains why changing it has a cost.

To verify a different disk count, compare the final total with 2^n − 1. For example, four disks require fifteen moves. If the displayed count differs, inspect the counter increment and make sure it happens once between the two recursive calls.

The count describes the shortest legal solution when there are three pegs and disks keep their size order. The algorithm does not search through alternative move sequences. Its recursive construction reaches the lower bound because the largest disk cannot move until every smaller disk is stacked on the spare peg, and the smaller stack must then be moved back over it.

When the compiler reports an input-related warning, keep the validation in place rather than casting the value before checking it. The program reads into int first, verifies the conversion and bounds, and only then converts to unsigned int for the recursive count. That order ensures a negative value cannot turn into a very large unsigned count.

For the smallest permitted input, one disk, the program emits one line: disk one moves from A to C. This case checks both the base case and the initial peg roles. A result from A to B usually means the final two peg arguments were reversed in the initial call.

Conclusion: Track the Peg Roles

The recursive solution works by clearing the smaller stack, moving the largest disk once, and putting the smaller stack back on top. Keeping source, helper and destination in the same argument order makes each recursive call simpler to check.

For another explanation of the recursive decomposition, see Carnegie Mellon’s Towers of Hanoi recursion notes. The GeeksforGeeks C example also shows a C implementation and move output.

FAQ

These answers cover the move count and the role of the helper peg.

How many moves does Tower of Hanoi take?

The minimum number is 2^n − 1 for n disks. Three disks take seven moves.

Why does the recursive call swap the helper and destination pegs?

The first call moves the smaller stack onto the helper peg, so the destination peg temporarily serves as its helper. The second call starts from that helper peg and moves the stack to the destination.

Ninad Pathak
Ninad Pathak

Ninad Pathak is a founding member and Editor in Chief at CodeForGeek. He writes about practical AI tooling and developer workflows, and outside work you will likely find him with a book, hot brewed coffee, and ambient music.

Articles: 80