Tower of Hanoi Problem in DSA C - Execution Trace

Concept Flow - Tower of Hanoi Problem

Start with all disks on Source

↓

Move n-1 disks from Source to Auxiliary

↓

Move largest disk from Source to Destination

↓

Move n-1 disks from Auxiliary to Destination

↓

All disks moved to Destination

The Tower of Hanoi moves disks recursively: first move smaller disks to auxiliary, then largest disk to destination, then smaller disks from auxiliary to destination.

Execution Sample

DSA C

void hanoi(int n, char src, char aux, char dest) {
  if (n == 1) {
    printf("Move disk 1 from %c to %c\n", src, dest);
    return;
  }
  hanoi(n-1, src, dest, aux);
  printf("Move disk %d from %c to %c\n", n, src, dest);
  hanoi(n-1, aux, src, dest);
}

This code prints the steps to move n disks from source to destination using auxiliary.

Execution Table

Step	Operation	Disks Moved	From Peg	To Peg	Recursive Call	Visual State
1	Move disk 1	1	A	C	No	[A:3,2] [B:] [C:1]
2	Move disk 2	2	A	B	Yes	[A:3] [B:2] [C:1]
3	Move disk 1	1	C	B	No	[A:3] [B:2,1] [C:]
4	Move disk 3	3	A	C	No	[A:] [B:2,1] [C:3]
5	Move disk 1	1	B	A	No	[A:1] [B:2] [C:3]
6	Move disk 2	2	B	C	Yes	[A:1] [B:] [C:3,2]
7	Move disk 1	1	A	C	No	[A:] [B:] [C:3,2,1]
8	All disks moved	3	-	-	No	[A:] [B:] [C:3,2,1]

💡 All disks moved from Source (A) to Destination (C) following rules.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
Peg A	[3,2,1]	[3,2]	[3]	[3]	[]	[1]	[1]	[]	[]
Peg B	[]	[]	[2]	[2,1]	[2,1]	[2]	[]	[]	[]
Peg C	[]	[1]	[1]	[]	[3]	[3]	[3,2]	[3,2,1]	[3,2,1]

Key Moments - 3 Insights

Why do we move n-1 disks first before moving the largest disk?

Because the largest disk can only be moved when the smaller disks above it are out of the way, as shown in steps 1-3 in the execution_table.

Why do we use recursion twice in the function?

The first recursion moves n-1 disks to auxiliary peg, and the second moves them from auxiliary to destination after moving the largest disk, as seen in steps 2 and 6.

How do we know when the recursion stops?

When n equals 1, the base case is reached and a single disk is moved directly, as in step 1 and other single disk moves.

Visual Quiz - 3 Questions

Look at the execution_table, at which step is the largest disk moved from Source to Destination?

A Step 3

B Step 6

C Step 4

D Step 7

💡 Hint

Check the 'Operation' and 'Disks Moved' columns in execution_table for the largest disk move.

According to variable_tracker, what is the state of Peg B after Step 3?

A [2,1]

B [2]

C []

D [3]

💡 Hint

Look at the Peg B row and the 'After Step 3' column in variable_tracker.

If we increase the number of disks to 4, how would the number of steps in execution_table change?

A It would stay the same

B It would increase exponentially

C It would double

D It would decrease

💡 Hint

Recall Tower of Hanoi requires 2^n - 1 moves; increasing disks increases steps exponentially.

Concept Snapshot

Tower of Hanoi moves n disks from Source to Destination using Auxiliary.
Move n-1 disks to Auxiliary,
Move largest disk to Destination,
Move n-1 disks from Auxiliary to Destination.
Base case: move single disk directly.
Total moves: 2^n - 1.

Full Transcript

The Tower of Hanoi problem moves disks between three pegs following rules: only one disk at a time, larger disks cannot be placed on smaller disks. The recursive solution moves n-1 disks to auxiliary peg, then moves the largest disk to destination, then moves n-1 disks from auxiliary to destination. The base case moves a single disk directly. The execution table shows each move step-by-step, and the variable tracker shows peg states after each step. This helps visualize how disks shift between pegs until all are moved to the destination peg.