Tower Of Hanoi Recursion In C

The Tower of Hanoi is a classic puzzle that beautifully illustrates the power of recursion, and implementing its solution in C provides a clear, hands‑on way to see how recursive functions break down a complex problem into simpler sub‑problems. In this article we explore the logic behind the Tower of Hanoi recursion in C, walk through a complete, annotated program, analyze its time and space complexity, and answer common questions that arise when learners first encounter this elegant algorithm. By the end, you will not only be able to write the code yourself but also appreciate why recursion is such a natural fit for this timeless challenge Not complicated — just consistent..

Worth pausing on this one.

Understanding the Tower of Hanoi Problem

The puzzle consists of three pegs (usually labeled A, B, and C) and a number of disks of different sizes that can slide onto any peg. At the start, all disks are stacked on peg A in decreasing size order, with the largest disk at the bottom and the smallest at the top. The objective is to move the entire stack to another peg—commonly peg C—while obeying two rules:

1. Only one disk may be moved at a time.
2. A larger disk may never be placed on top of a smaller disk.

Although the rules are simple, the minimum number of moves required grows exponentially with the number of disks: (2^n - 1), where n is the disk count. This exponential growth hints at a recursive structure: moving n disks can be expressed in terms of moving n‑1 disks twice, with a single move of the largest disk in between.

Recursive Solution Explained

Recursion solves a problem by having a function call itself with a smaller instance of the same problem, eventually reaching a base case that can be solved directly. For the Tower of Hanoi, the recursive algorithm follows these steps:

1. Move the top n‑1 disks from the source peg to the auxiliary peg, using the destination peg as a temporary holder.
2. Move the largest disk (the n‑th disk) directly from the source peg to the destination peg.
3. Move the n‑1 disks from the auxiliary peg onto the destination peg, using the source peg as a temporary holder.

When n equals 1, the base case is triggered: we simply move the single disk from source to destination. Each recursive call reduces the problem size by one, guaranteeing termination.

Why Recursion Fits Naturally

The Tower of Hanoi exhibits self‑similarity: the sub‑problem of moving n‑1 disks mirrors the original problem, only with different peg roles. This self‑similarity is the hallmark of problems that recursion solves efficiently. Beyond that, the recursive description mirrors the human intuition of “first clear the way, move the biggest piece, then rebuild the stack No workaround needed..

Implementing the Algorithm in C

Below is a complete, self‑contained C program that solves the Tower of Hanoi for any number of disks entered by the user. The code includes detailed comments to highlight each part of the recursion Which is the point..

#include 

/* Function prototype */
void towerOfHanoi(int n, char source, char auxiliary, char destination);

int main() {
    int disks;
    printf("Enter the number of disks: ");
    if (scanf("%d", &disks) != 1 || disks < 1) {
        printf("Please enter a positive integer.\n");
        return 1;
    }
    printf("\nSequence of moves to solve Tower of Hanoi with %d disks:\n\n", disks);
    towerOfHanoi(disks, 'A', 'B', 'C');   // A: source, B: auxiliary, C: destination
    return 0;
}

/*
 * Recursively prints the moves required to transfer n disks
 * from the source peg to the destination peg using the auxiliary peg.
 */
void towerOfHanoi(int n, char source, char auxiliary, char destination) {
    if (n == 1) {                         // Base case: only one disk
        printf("Move disk 1 from %c to %c\n", source, destination);
        return;
    }
    // Step 1: Move n-1 disks from source to auxiliary
    towerOfHanoi(n - 1, source, destination, auxiliary);
    // Step 2: Move the nth disk from source to destination
    printf("Move disk %d from %c to %c\n", n, source, destination);
    // Step 3: Move n-1 disks from auxiliary to destination
    towerOfHanoi(n - 1, auxiliary, source, destination);
}

Code Walk‑through

• Header: #include <stdio.h> provides input/output facilities.
• Function prototype: Declares towerOfHanoi before main so the compiler knows its signature.
• main function:
  • Prompts the user for the number of disks.
  • Validates input to ensure a positive integer.
  • Calls towerOfHanoi with peg labels 'A' (source), 'B' (auxiliary), and 'C' (destination).
• Recursive function:
  • Base case (n == 1): prints the single move.
  • Recursive case:
    • First call moves n‑1 disks to the auxiliary peg.
    • Second printf moves the largest disk.
    • Third call moves the n‑1 disks from auxiliary to destination.

When you compile (gcc -o hanoi hanoi.c) and run the program, it prints each move in the exact order needed to solve the puzzle.

Step‑by‑Step Example (3 Disks)

To solidify understanding, let’s trace the output for three disks:

Enter the number of disks: 3

Sequence of moves to solve Tower of Hanoi with 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

Notice how the algorithm first solves the 2‑disk sub‑problem (moving disks 1 and 2 to peg B), then moves the largest disk, and finally solves the 2‑disk sub‑problem again to finish on peg C Worth knowing..

Complexity Analysis

Time Complexity

Each call to towerOfHanoi results in two recursive calls for n‑1 disks plus a constant amount of work (the printf). This yields the recurrence relation:

[ T(n) = 2T(n-1) + O(1) ]

Solving this recurrence gives:

[ T(n) = 2^n - 1 ]

Thus, the time complexity is O(2ⁿ), matching the known minimal move count.

Space Complexity

The depth of the recursion stack equals n because each call waits for its two subcalls to finish before returning. That's why, the

Beyond the straightforward recursive formulation, developers often explore alternative strategies to tame the exponential blow‑up or to adapt the algorithm to different environments Not complicated — just consistent..

Iterative simulation
One common approach replaces the implicit call stack with an explicit stack data structure. By pushing the state of each sub‑problem (the current values of n, source, auxiliary, and destination) onto a manual stack, the algorithm can be executed in a loop rather than relying on the language’s call stack. This eliminates the risk of stack overflow when n becomes large, though the asymptotic number of moves — 2ⁿ − 1 — remains unchanged.

Bit‑wise insight
Observing the pattern of moves reveals that the smallest disk traverses the pegs in a cyclic order. When the total number of disks is odd, it moves from source to destination to auxiliary and repeats; when even, the direction of the smallest disk’s step is reversed. Leveraging this regularity, an iterative solution can compute each move directly from the move count without recursion, using simple arithmetic or bitwise operations.

Generalised pegs
The classic three‑peg version assumes the minimal number of moves. With four or more pegs, the optimal strategy is described by the Frame‑Stewart algorithm, which recursively partitions the disks into two groups and solves each subgroup on a subset of pegs. While the exact minimal move count for more than three pegs is still a subject of research, the recursive mindset introduced by the three‑peg case extends naturally to these variants.

Educational impact
Regardless of the implementation style, the puzzle serves as a concise illustration of several fundamental concepts:

• Divide‑and‑conquer – the problem is broken into two smaller sub‑problems of size n − 1.
• Recursion depth – the call stack grows linearly with n, highlighting the importance of managing resources.
• Exponential growth – the move count doubles with each additional disk, providing a tangible example of exponential complexity.

Conclusion
The tower of Hanoi remains a timeless teaching tool that blends mathematical elegance with practical algorithmic considerations. Its recursive solution showcases how a simple rule can generate a complex, optimal sequence, while iterative and generalized adaptations demonstrate how to address real‑world constraints such as stack limits and additional resources. Whether used to introduce recursion in a classroom or to benchmark performance in a production setting, the puzzle continues to inspire both learners and seasoned programmers alike The details matter here..