Tower of Hanoi: flowchart, algorithm and program
This program reads the number of disks n and prints every move needed to shift all disks from peg A to peg C, using peg B as the helper. The idea is recursive: to move n disks, first move n-1 disks out of the way, move the biggest disk, then bring the n-1 disks back on top of it.
▶ Watch the dry run step by step →
Algorithm
- Step 1: Start.
- Step 2: Print "Enter n: ".
- Step 3: Read n.
- Step 4: Call hanoi(n, 'A', 'C', 'B').
- Step 5: If n == 1, go to step 6; otherwise go to step 7.
- Step 6: Print Move disk 1 from -> to. Go to step 10.
- Step 7: hanoi(n-1, from, aux, to).
- Step 8: Print Move disk n from -> to.
- Step 9: hanoi(n-1, aux, to, from).
- Step 10: Return to caller.
- Step 11: Stop.
Program in C, Python and Java
Tower of Hanoi program in C
#include <stdio.h>
void hanoi(int n, char from, char to, char aux) {
if (n == 1) {
printf("Move disk 1 from %c to %c\n", from, to);
return;
}
hanoi(n - 1, from, aux, to);
printf("Move disk %d from %c to %c\n", n, from, to);
hanoi(n - 1, aux, to, from);
}
int main() {
int n;
printf("Enter n: ");
scanf("%d", &n);
hanoi(n, 'A', 'C', 'B');
return 0;
}Tower of Hanoi program in Python
def hanoi(n, source, target, aux):
if n == 1:
print("Move disk 1 from", source, "to", target)
return
hanoi(n - 1, source, aux, target)
print("Move disk", n, "from", source, "to", target)
hanoi(n - 1, aux, target, source)
n = int(input("Enter n: "))
hanoi(n, 'A', 'C', 'B')Tower of Hanoi program in Java
import java.util.Scanner;
public class Main {
static void hanoi(int n, char from, char to, char aux) {
if (n == 1) {
System.out.println("Move disk 1 from " + from + " to " + to);
return;
}
hanoi(n - 1, from, aux, to);
System.out.println("Move disk " + n + " from " + from + " to " + to);
hanoi(n - 1, aux, to, from);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter n: ");
int n = sc.nextInt();
hanoi(n, 'A', 'C', 'B');
}
}
Sample input: n = 3
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
How it works
- hanoi(n, from, to, aux) moves n disks from the peg `from` to the peg `to`, using `aux` as the spare peg. main() calls it as hanoi(n, 'A', 'C', 'B').
- Base case: if n == 1, there is only one disk, so print 'Move disk 1 from from to to' and return. This stops the recursion.
- Recursive step 1: hanoi(n - 1, from, aux, to) moves the top n-1 disks from `from` to `aux`, so the largest disk is free.
- Then the program prints the move of disk n from `from` to `to`.
- Recursive step 2: hanoi(n - 1, aux, to, from) moves the n-1 disks from `aux` onto `to`, on top of the largest disk.
- The number of moves is 2^n - 1, so n = 3 prints 7 moves and n = 2 prints 3 moves.
Dry run (trace table)
| Step | Line | Box | n | from | to | aux | Output |
|---|---|---|---|---|---|---|---|
| 1 | 13 | Start | |||||
| 2 | 15 | Print "Enter n: " | Enter n: | ||||
| 3 | 16 | Read n | 3 | ||||
| 4 | 17 | Call hanoi(n, 'A', 'C', 'B') | 3 | ||||
| 5 | 4 | n == 1? | 3 | A | C | B | |
| 6 | 8 | hanoi(n-1, from, aux, to) | 3 | A | C | B | |
| 7 | 4 | n == 1? | 2 | A | B | C | |
| 8 | 8 | hanoi(n-1, from, aux, to) | 2 | A | B | C | |
| 9 | 4 | n == 1? | 1 | A | C | B | |
| 10 | 5 | Print Move disk 1 from -> to | 1 | A | C | B | Move disk 1 from A to C |
| 11 | 6 | Return to caller | 1 | A | C | B | |
| 12 | 9 | Print Move disk n from -> to | 2 | A | B | C | Move disk 2 from A to B |
| 13 | 10 | hanoi(n-1, aux, to, from) | 2 | A | B | C | |
| 14 | 4 | n == 1? | 1 | C | B | A | |
| 15 | 5 | Print Move disk 1 from -> to | 1 | C | B | A | Move disk 1 from C to B |
| 16 | 6 | Return to caller | 1 | C | B | A | |
| 17 | 11 | Return to caller | 2 | A | B | C | |
| 18 | 9 | Print Move disk n from -> to | 3 | A | C | B | Move disk 3 from A to C |
| 19 | 10 | hanoi(n-1, aux, to, from) | 3 | A | C | B | |
| 20 | 4 | n == 1? | 2 | B | C | A |
Time and space complexity
Time: O(2^n) · Space: O(n). Each call makes two calls on n-1 disks, giving 2^n - 1 moves, and the recursion depth is n.
Common mistakes
- Forgetting the base case n == 1, which makes the function call itself forever and crash with a stack overflow.
- Passing the pegs in the wrong order in the recursive calls, for example using (from, to, aux) in both calls, which gives illegal moves.
- Printing 'disk 1' for every move instead of using n in the middle print, so the disk number in the output is wrong.
Viva questions
Q1. What is the base case in your hanoi function, and why is it needed?
The base case is n == 1 on line 4, where we just print one move and return. Without it the function would keep calling itself with smaller n forever and the stack would overflow.
Q2. In the first recursive call hanoi(n-1, from, aux, to), why are 'to' and 'aux' swapped?
The top n-1 disks must go out of the way onto the spare rod, so aux becomes the destination and 'to' becomes the helper. After that, the largest disk can move straight from 'from' to 'to'.
Q3. Explain the three steps the function performs for n disks.
First it moves n-1 disks from source to auxiliary (line 8), then it moves the largest disk n from source to destination (line 9), then it moves the n-1 disks from auxiliary to destination (line 10).
Q4. For n = 3, how many moves are printed and what is the very first move?
It prints 2^3 - 1 = 7 moves. The first move is 'Move disk 1 from C to B'? No: with n=3 the first printed move is 'Move disk 1 from A to C', because the smallest disk moves to the destination when the number of disks is odd.
Q5. What happens if the user enters 0 or a negative number?
The base case n == 1 is never hit, so n keeps decreasing through 0, -1, -2 and so on and the recursion never ends, causing a stack overflow crash. Adding a check like if (n <= 0) return; would fix it.
Q6. What is the time complexity of this program, and what about the recursion depth?
The time complexity is O(2^n) because T(n) = 2T(n-1) + 1, giving 2^n - 1 moves. The recursion depth, and so the stack space, is only O(n).
Q7. Why does line 9 print 'disk %d' with n, while line 5 always prints 'disk 1'?
In the base case n is 1, so the disk moved is disk 1. In the general case the disk being moved is the largest one of the current sub-problem, which is disk number n.
Q8. What would change if you wanted to move the disks from rod A to rod B instead of C?
Only the call in main changes, to hanoi(n, 'A', 'B', 'C'), because the function takes the rods as parameters. The logic and the number of moves stay the same.
Frequently asked questions
How many moves does the Tower of Hanoi need for n disks?
It needs 2^n - 1 moves. For n = 2 that is 3 moves and for n = 3 it is 7 moves, which matches the sample output.
Why do the peg names swap in the recursive calls?
Each call has a different job. In the first call the target is the helper peg (aux), and in the second call the start is the helper peg, so `to` and `aux` (or `from` and `aux`) swap places.
Why does the program use n = 2 or 3 only?
The output doubles with every extra disk, so larger n prints a very long list. Small values keep the output short enough to follow and dry run by hand.