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

  1. Step 1: Start.
  2. Step 2: Print "Enter n: ".
  3. Step 3: Read n.
  4. Step 4: Call hanoi(n, 'A', 'C', 'B').
  5. Step 5: If n == 1, go to step 6; otherwise go to step 7.
  6. Step 6: Print Move disk 1 from -> to. Go to step 10.
  7. Step 7: hanoi(n-1, from, aux, to).
  8. Step 8: Print Move disk n from -> to.
  9. Step 9: hanoi(n-1, aux, to, from).
  10. Step 10: Return to caller.
  11. 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)

StepLineBoxnfromtoauxOutput
113Start
215Print "Enter n: "Enter n:
316Read n3
417Call hanoi(n, 'A', 'C', 'B')3
54n == 1?3ACB
68hanoi(n-1, from, aux, to)3ACB
74n == 1?2ABC
88hanoi(n-1, from, aux, to)2ABC
94n == 1?1ACB
105Print Move disk 1 from -> to1ACBMove disk 1 from A to C
116Return to caller1ACB
129Print Move disk n from -> to2ABCMove disk 2 from A to B
1310hanoi(n-1, aux, to, from)2ABC
144n == 1?1CBA
155Print Move disk 1 from -> to1CBAMove disk 1 from C to B
166Return to caller1CBA
1711Return to caller2ABC
189Print Move disk n from -> to3ACBMove disk 3 from A to C
1910hanoi(n-1, aux, to, from)3ACB
204n == 1?2BCA

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.

More programs

← All programs

Try AI Flowchart free →