What is Tower of Hanoi in C- C Programming Course in Telugu

Need Help or More Information?

Questions about this free C programming course, embedded C training or career guidance? Get in touch.

Free C Programming Course | Functions | Lecture 37

Tower of Hanoi in C

Solve the Tower of Hanoi in C with recursion: learn the rules, work out the solutions for one, two and three disks, discover the general pattern, and turn it into a clean program.

Welcome to the next lecture of our free C programming course. Today we solve the Tower of Hanoi in C, the puzzle that makes recursion click for most students. Unlike factorial or Fibonacci, there is no obvious loop for this problem, yet a three-line recursive idea solves it for any number of disks. This free C tutorial also connects the puzzle to C programming for embedded systems: we examine recursion depth, the exponential number of moves, and how to test a recursive function with a built-in self-check.

If you are working through our free embedded C course in order, you already understand winding, unwinding and the base case. Now you will see recursion used as a real problem-solving tool, not just a way to compute a formula.

What You Will Learn

  • The setup and the two rules of the Tower of Hanoi puzzle
  • How to solve the puzzle by hand for 1, 2 and 3 disks
  • How to discover the general three-step recursive solution from small cases
  • How to write the Tower of Hanoi in C with clean parameter naming
  • Why the number of moves is two to the power n minus one
  • How recursion depth stays small even when the move count explodes

Prerequisites

  • The previous lectures on factorial, power and Fibonacci recursion
  • Function parameters of type char and unsigned
  • Using printf with several format specifiers

The Tower of Hanoi Puzzle Explained

You are given three pegs. Call them S for source, D for destination and T for temporary. The source peg holds a stack of disks sorted by size, with the largest at the bottom and the smallest on top. The goal is to move the entire stack onto the destination peg, keeping the same order, using the temporary peg whenever you need a parking place.

Roles of the three pegs and the two rules
ItemMeaning
Peg S (source)Where all disks start
Peg D (destination)Where all disks must finish
Peg T (temporary)Helper peg for parking disks
Rule 1Move exactly one disk at a time, always the top disk of a peg
Rule 2Never place a larger disk on top of a smaller one

Solving the Tower of Hanoi by Hand for Small Cases

Experienced programmers rarely start with code. They solve tiny versions by hand and look for a pattern. We number the disks from 1 (smallest) upward. A move written S to D means: take the top disk of peg S and put it on peg D.

One Disk

Trivial: a single move, S to D.

Two Disks

Two disks: 3 moves
StepMovePeg S (bottom to top)Peg TPeg D
Start–2, 1emptyempty
1Disk 1: S to T21empty
2Disk 2: S to Dempty12
3Disk 1: T to Demptyempty2, 1

Three Disks

Three disks: 7 moves
StepMovePeg S (bottom to top)Peg TPeg D
Start–3, 2, 1emptyempty
1Disk 1: S to D3, 2empty1
2Disk 2: S to T321
3Disk 1: D to T32, 1empty
4Disk 3: S to Dempty2, 13
5Disk 1: T to S123
6Disk 2: T to D1empty3, 2
7Disk 1: S to Demptyempty3, 2, 1

Discovering the General Recursive Solution

Study the three-disk table. Moves 1 to 3 shift the upper two disks out of the way onto the temporary peg. Move 4 relocates the biggest disk, which is the only disk that could not have moved earlier. Moves 5 to 7 bring the two-disk stack from the temporary peg onto the destination. The two-disk puzzle is hiding inside the three-disk puzzle, twice. That observation is the whole algorithm.

General solution for n disks
1

Clear the top

Move the upper n minus 1 disks from S to T, using D as the helper peg.

2

Move the big one

Move disk number n, the largest, directly from S to D.

3

Rebuild on top

Move the n minus 1 disks from T to D, using S as the helper peg.

Steps 1 and 3 are smaller copies of the same puzzle, so they are solved by calling the same function. The only trick is that the pegs change roles. In step 1 the temporary peg becomes the target and the destination becomes the helper. In step 3 the source becomes the helper. Keeping that role swap straight is the hardest part of writing a correct Tower of Hanoi in C.

How peg roles rotate in the recursive calls (parameters: disks, from, via, to)
PhaseCall madeFromVia (helper)To
Original requesthanoi(n, S, T, D)STD
Step 1hanoi(n-1, S, D, T)SDT
Step 3hanoi(n-1, T, S, D)TSD

Tower of Hanoi in C: Complete Recursive Program

The function below takes the number of disks and three peg labels. The base case is zero disks, where there is nothing to do. Printing each move lets you watch the algorithm work.

#include <stdio.h>

static unsigned long step_no;     /* counts every disk move */

static void hanoi(unsigned disks, char from, char via, char to)
{
    if (disks == 0u) {
        return;                                   /* base case: nothing to move */
    }
    hanoi(disks - 1u, from, to, via);             /* park the upper stack on 'via' */

    step_no++;
    printf("Step %lu: disk %u  %c -> %c\n", step_no, disks, from, to);

    hanoi(disks - 1u, via, from, to);             /* bring the stack onto 'to' */
}

int main(void)
{
    unsigned n;

    printf("Number of disks (1 to 20): ");
    if (scanf("%u", &n) != 1 || n == 0u || n > 20u) {
        puts("Out of range");
        return 1;
    }

    hanoi(n, 'S', 'T', 'D');

    printf("Total moves: %lu (expected %lu)\n", step_no, (1ul << n) - 1ul);
    return 0;
}
$ gcc -Wall -Wextra -std=c11 -o hanoi hanoi.c
$ ./hanoi
Number of disks (1 to 20): 3
Step 1: disk 1  S -> D
Step 2: disk 2  S -> T
Step 3: disk 1  D -> T
Step 4: disk 3  S -> D
Step 5: disk 1  T -> S
Step 6: disk 2  T -> D
Step 7: disk 1  S -> D
Total moves: 7 (expected 7)

The program output matches the hand-built three-disk table exactly, which is a good sign that the role swapping is right. Notice that the printed disk number is simply the value of the disks parameter at the moment of the move: the call that owns disk k always moves disk k.

Self-Check Built into the Program

The last line compares the counted moves with the formula two to the power n minus one. A built-in check like this is a cheap form of unit test. In firmware you would turn it into an assertion that runs in debug builds.

Counting Moves: Why the Cost Explodes

Let M(n) be the number of moves for n disks. The algorithm moves n minus 1 disks twice and one disk once, so M(n) equals 2 times M(n minus 1) plus 1, with M(0) equal to 0. This resolves to two to the power n minus one.

Disks nMoves neededRecursion depth
112 (including the empty call)
374
5316
101,02311
201,048,57521
324,294,967,29533
6418,446,744,073,709,551,61565

Deep Insight

The depth of recursion grows by only one per extra disk, while the number of moves doubles. The stack is therefore never the bottleneck. Time is. Moving 64 disks at one move per second would take hundreds of billions of years.

Why Recursion Suits the Tower of Hanoi in C

Feature of the problemWhy recursion helps
Contains smaller copies of itselfThe n minus 1 sub-puzzles are solved by the same function
Natural stopping pointZero disks means nothing to do
State that must be remembered between phasesThe call stack stores which peg roles apply at each level
Hard to express with a plain loopAn iterative version needs an explicit stack or a clever bit trick

Real-World Use Cases

  • Backup rotation schedules for tape and disk media follow Hanoi-style patterns
  • A standard exercise to train divide-and-conquer thinking for interviews
  • A benchmark for checking that a compiler and stack configuration handle deep, regular recursion
  • A simple model of problems where a large task needs temporary storage while sub-tasks complete

Common Mistakes and Troubleshooting

SymptomCauseFix
A larger disk lands on a smaller oneHelper and target pegs swapped in a recursive callWrite the role table first and copy it into the calls
Wrong total move countCounter incremented in the wrong placeIncrement exactly once, just before printing a move
Output scrolls for agesLarge n with printing enabledLimit n or remove printing for benchmarks
Infinite recursionMissing base case or disks parameter not reducedReturn when disks equals zero and pass disks minus one
Shift overflow in the expected-moves checkShifting by the width of the typeRestrict n so the shift stays below the type width

Best Practices, Performance and Security

  • Name the pegs by role (from, via, to) instead of by letter inside the function.
  • Solve one, two and three cases on paper before writing code.
  • Keep side effects, such as printing, out of the recursive logic when you can, and pass a callback or counter instead.
  • Performance: the algorithm is optimal, because the minimum number of moves is exactly two to the power n minus one. You cannot make it faster, only cheaper per move.
  • Security: bound the disk count when it comes from user input, since a large value means an effectively endless run and a denial of service on a shared device.

Summary and Key Takeaways

  • The Tower of Hanoi has two rules: one disk at a time and never a larger disk on a smaller one.
  • Every n-disk solution is three steps: move n minus 1 away, move the biggest, move n minus 1 back.
  • The Tower of Hanoi in C uses a base case of zero disks and rotates the roles of the pegs.
  • Moves required equal two to the power n minus one; recursion depth is only about n.
  • Solve small cases by hand first, then generalise.

Conclusion

You have now solved a problem where recursion is the clearest tool available. You derived the algorithm from tiny cases, translated it into a working Tower of Hanoi in C, and proved its cost with a simple formula. These habits carry directly into embedded C programming: reduce the problem, define the exit, and always check the cost. The next lecture in this free C programming course gathers everything about recursion into a quiz and a set of interview questions.

Frequently Asked Questions

What is the Tower of Hanoi problem in C programming?

It is a puzzle about moving a stack of disks between three pegs under two rules, commonly used to teach recursion by writing a function that prints the sequence of moves.

What is the minimum number of moves for n disks?

Two to the power n minus one. Three disks need 7 moves and four disks need 15.

What is the base case in the Tower of Hanoi recursion?

When there are zero disks to move the function simply returns. Some versions stop at one disk and print the single move instead.

How deep does the recursion go?

About n levels for n disks, so stack use is small even though the number of moves is huge.

Can the Tower of Hanoi be solved without recursion?

Yes, with an explicit stack or with a known iterative pattern, but the recursive version is far shorter and easier to verify.

Why do the peg parameters change order in each recursive call?

Because the sub-puzzle has a different source, helper and target than its parent. Swapping them correctly is what keeps the larger disk off smaller disks.

Free Embedded C Course

Finish the recursion topic with the quiz and interview questions in the next lecture, and keep building your skills with EmbeddedPathashala.

Need Help or More Information?

Questions about this free C programming course, embedded C training or career guidance? Get in touch.

2 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *