Tower of Hanoi
In this page:
Problem Idea
Tower of Hanoi is a classic puzzle where you must move a stack of differently-sized disks from one rod to another, using a third rod as helper, never placing a larger disk on top of a smaller one. It's a favorite recursion teaching example because the recursive solution is dramatically simpler than trying to plan the moves directly.
Example: Problem Idea
#include <iostream>
using namespace std;
int main() {
cout << "Move 3 disks from rod A to rod C using rod B as helper";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Move 3 disks from rod A to rod C using rod B as helper");
}
}print("Move 3 disks from rod A to rod C using rod B as helper")#include <stdio.h>
int main() {
printf("Move 3 disks from rod A to rod C using rod B as helper");
return 0;
}Login to try C/C++/Java code in the editor
Recursive Rule
The recursive insight is to treat the top n-1 disks as one group: move that whole group out of the way to the helper rod, move the single largest disk directly to the target, then move the n-1 group from the helper rod on top of it. Each of those two n-1 moves is just a smaller version of the same problem.
Example: Recursive Rule
#include <iostream>
using namespace std;
void hanoi(int n, char from, char to, char via) {
if (n == 0) return;
hanoi(n - 1, from, via, to);
cout << "Move disk " << n << " from " << from << " to " << to << endl;
hanoi(n - 1, via, to, from);
}
int main() {
hanoi(3, 'A', 'C', 'B');
return 0;
}public class Main {
static void hanoi(int n, char from, char to, char via) {
if (n == 0) return;
hanoi(n - 1, from, via, to);
System.out.println("Move disk " + n + " from " + from + " to " + to);
hanoi(n - 1, via, to, from);
}
public static void main(String[] args) {
hanoi(3, 'A', 'C', 'B');
}
}def hanoi(n, frm, to, via):
if n == 0:
return
hanoi(n - 1, frm, via, to)
print("Move disk", n, "from", frm, "to", to)
hanoi(n - 1, via, to, frm)
hanoi(3, 'A', 'C', 'B')#include <stdio.h>
void hanoi(int n, char from, char to, char via) {
if (n == 0) return;
hanoi(n - 1, from, via, to);
printf("Move disk %d from %c to %c\n", n, from, to);
hanoi(n - 1, via, to, from);
}
int main() {
hanoi(3, 'A', 'C', 'B');
return 0;
}Login to try C/C++/Java code in the editor
Base Case
The base case is a single disk, which just moves directly from its current rod to the target rod in one step — no further recursion needed. Without this stopping point, the 'move n-1 disks' step would keep asking to move even smaller groups forever.
Example: Base Case
#include <iostream>
using namespace std;
void hanoi(int n, char from, char to, char via) {
if (n == 1) { cout << "Move disk 1 from " << from << " to " << to << endl; return; }
hanoi(n - 1, from, via, to);
cout << "Move disk " << n << " from " << from << " to " << to << endl;
hanoi(n - 1, via, to, from);
}
int main() {
hanoi(2, 'A', 'C', 'B');
return 0;
}public class Main {
static void hanoi(int n, char from, char to, char via) {
if (n == 1) { System.out.println("Move disk 1 from " + from + " to " + to); return; }
hanoi(n - 1, from, via, to);
System.out.println("Move disk " + n + " from " + from + " to " + to);
hanoi(n - 1, via, to, from);
}
public static void main(String[] args) {
hanoi(2, 'A', 'C', 'B');
}
}def hanoi(n, frm, to, via):
if n == 1:
print("Move disk 1 from", frm, "to", to)
return
hanoi(n - 1, frm, via, to)
print("Move disk", n, "from", frm, "to", to)
hanoi(n - 1, via, to, frm)
hanoi(2, 'A', 'C', 'B')#include <stdio.h>
void hanoi(int n, char from, char to, char via) {
if (n == 1) { printf("Move disk 1 from %c to %c\n", from, to); return; }
hanoi(n - 1, from, via, to);
printf("Move disk %d from %c to %c\n", n, from, to);
hanoi(n - 1, via, to, from);
}
int main() {
hanoi(2, 'A', 'C', 'B');
return 0;
}Login to try C/C++/Java code in the editor
Understanding the Process
This three-step pattern — move the smaller group away, move the big piece, move the smaller group back on top — repeats at every level of recursion, just with fewer disks and swapped rod roles each time. Tracing it for 3 disks by hand makes the pattern click before reasoning about it abstractly.
Example: Understanding the Process
#include <iostream>
using namespace std;
int moveCount = 0;
void hanoi(int n, char from, char to, char via) {
if (n == 0) return;
hanoi(n - 1, from, via, to);
moveCount++;
hanoi(n - 1, via, to, from);
}
int main() {
hanoi(3, 'A', 'C', 'B');
cout << "Total moves: " << moveCount;
return 0;
}public class Main {
static int moveCount = 0;
static void hanoi(int n, char from, char to, char via) {
if (n == 0) return;
hanoi(n - 1, from, via, to);
moveCount++;
hanoi(n - 1, via, to, from);
}
public static void main(String[] args) {
hanoi(3, 'A', 'C', 'B');
System.out.println("Total moves: " + moveCount);
}
}move_count = 0
def hanoi(n, frm, to, via):
global move_count
if n == 0:
return
hanoi(n - 1, frm, via, to)
move_count += 1
hanoi(n - 1, via, to, frm)
hanoi(3, 'A', 'C', 'B')
print("Total moves:", move_count)#include <stdio.h>
int moveCount = 0;
void hanoi(int n, char from, char to, char via) {
if (n == 0) return;
hanoi(n - 1, from, via, to);
moveCount++;
hanoi(n - 1, via, to, from);
}
int main() {
hanoi(3, 'A', 'C', 'B');
printf("Total moves: %d", moveCount);
return 0;
}Login to try C/C++/Java code in the editor
Practice
Solving n disks takes 2^n - 1 moves minimum, which is why Tower of Hanoi is also used to illustrate how quickly exponential growth becomes impractical — 20 disks alone requires over a million moves.
Example: Practice
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int n = 4;
cout << "Minimum moves for " << n << " disks: " << (int)pow(2, n) - 1;
return 0;
}public class Main {
public static void main(String[] args) {
int n = 4;
System.out.println("Minimum moves for " + n + " disks: " + ((int) Math.pow(2, n) - 1));
}
}n = 4
print("Minimum moves for", n, "disks:", 2 ** n - 1)#include <stdio.h>
#include <math.h>
int main() {
int n = 4;
printf("Minimum moves for %d disks: %d", n, (int)pow(2, n) - 1);
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 7 topics to unlock
0/7 topics done
Complete these topics first: