Tower of Hanoi · Data Structures and Algorithms

Tower of Hanoi

CSC-211 · Semester III · Data Structures and Algorithms

intermediate25 minAvailable

RecursionFunction call stack · divide & conquer

n =

Lab brief

Objective

Solve the Tower of Hanoi puzzle recursively and observe the exponential 2ⁿ−1 move count and the recursive structure of each move.

Theory & concepts

To move n disks from source to destination using an auxiliary peg, first move n−1 disks onto the auxiliary peg, move the largest disk to the destination, then move the n−1 disks on top of it. This recursive strategy produces exactly 2ⁿ − 1 moves. The disk-1 move happens every other step, alternating between pegs.

Rendering diagram…

Recursive structure of Tower of Hanoi

hanoi(n, src, aux, dst):
  if n == 1 → move disk 1 from src to dst
  else
    hanoi(n-1, src, dst, aux)
    move disk n from src to dst
    hanoi(n-1, aux, src, dst)
Moves for n disks = 2ⁿ − 1

Prerequisites

Lab: Recursion — Factorial and Fibonacci
The rules of the Tower of Hanoi puzzle

Instructions

1Choose the number of disks (3–6).
2Step through each recursive move and watch the disks transfer.
3Follow the largest disk: it moves exactly once, at the midpoint.
4Count the total moves and confirm it equals 2ⁿ − 1.

Tasks

Three disks
Verify the solution completes in exactly 7 moves.
Largest disk
Confirm disk n moves only once, at move 2ⁿ⁻¹.
Exponential growth
Add one disk and note the move count doubles plus one.

Self-check

The simulation obeys the three-pole rules.
Total moves match 2ⁿ − 1.
The recursive structure of moves is described.

Environment

disk count slidermove steppermove counterrecursive decomposition