Tower of Hanoi

Move n disks between three pegs, never placing larger on smaller. The recursive insight: move n−1 aside, move the big disk, move n−1 back on top. Exactly 2ⁿ−1 moves.

Category

Recursion

Time complexity

O(2ⁿ)

Space complexity

O(n)

Pseudocode

hanoi(n, from, to, via):
  hanoi(n−1, from, via, to)
  move disk n: from → to
  hanoi(n−1, via, to, from)

Reference implementation

def hanoi(n, a, c, b):
    if n == 0: return
    hanoi(n-1, a, b, c)
    move(n, a, c)
    hanoi(n-1, b, c, a)

Open the interactive Tower of Hanoi visualisation →