Tower of Hanoi - Algorithm Tutorial | Repovive

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/algorithms/tower-of-hanoi

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/algorithms/tower-of-hanoi

Repovive

Tower of Hanoi - Algorithm Tutorial | Repovive | Repovive

Recursive Algorithm

The algorithm follows directly from the insight:

function hanoi(n, source, auxiliary, destination):
    if n == 1:
        print source + destination
        return

    // Step 1: Move n-1 disks from source to auxiliary
    hanoi(n - 1, source, destination, auxiliary)

    // Step 2: Move largest disk from source to destination
    print source + destination

    // Step 3: Move n-1 disks from auxiliary to destination
    hanoi(n - 1, auxiliary, source, destination)

Notice how the pegs swap roles in recursive calls:

In step 1: destination becomes auxiliary, auxiliary becomes destination
In step 3: auxiliary becomes source, source becomes auxiliary

This "role swapping" makes the algorithm work correctly.

Complexity Analysis

Time Complexity: $O(2^n)$

Let $T(n)$ = number of moves for $n$ disks.

Recurrence: $T(n) = 2 \cdot T(n-1) + 1$

Base case: $T(1) = 1$

Solving: $T(n) = 2^n - 1$

This is optimal. It is mathematically proven that you cannot solve the puzzle in fewer than $2^n - 1$ moves.

Space Complexity: $O(n)$

The recursion depth is $n$ (one level per disk size), so the call stack uses $O(n)$ space.

Growth rate:

$n$	Moves
5	31
10	1,023
15	32,767
20	1,048,575

Tower of Hanoi Algorithm Tutorial

Introduction

The Key Insight

Practice this Algorithm

Related Algorithms

Recursive Algorithm

Complexity Analysis

Key Takeaways