# Tower of Hanoi

The classic puzzle of moving a stack of disks between pegs, whose recursive solution is three lines and whose cost is exponential.

**Rests on:** Recursive Thinking, Stack Memory Behaviour

*Mathematical Foundations · Recursion*


## Why learn this

This puzzle teaches you how to solve a difficult problem by breaking it down into a simpler version of itself. You might wonder why this matters beyond a game. It shows that even the most elegant, logical instructions can become incredibly slow or require an enormous amount of memory when the numbers get large. For example, moving just 64 disks requires more than 18 quintillion moves—more time than the universe has existed. Understanding this helps you judge whether a simple idea will work in the real world or if it will grind to a halt as the task grows.


## The intuition

Imagine three pegs standing on a table and a stack of six disks, each smaller than the one below it, all starting on the left peg. Your goal is to move the entire stack to the right peg. You can only move one disk at a time, and you can never place a larger disk on top of a smaller one. The middle peg serves as a temporary resting spot.

The secret is to stop thinking about all six disks at once. Instead, focus on the bottom-most disk—the largest one. It cannot move until every other disk is out of its way. So, your first major task is simply to get the top five disks onto the middle peg. Once that is done, you move the large bottom disk from the left peg to the right peg. Now, your second major task is to move those five disks from the middle peg to the right peg, on top of the large one.

Notice the pattern? To move a stack of five disks, you first need to get the top four out of the way, move the fifth disk, and then bring the four back. You keep splitting the problem in half until you reach a stack of just one disk. Moving one single disk is trivial—it’s already solved. Because you know how to solve the one-disk case, and you know that moving n-1 disks is just a smaller version of the same task, the entire six-disk puzzle resolves itself automatically. Each step relies on the success of the smaller steps beneath it.


## An analogy

Think of clearing a messy desk with a stack of twelve books. You want to move the stack from the left side of the desk to the right side without dropping any books or placing a heavy book on top of a thin one. The only way to reach the bottom book is to clear everything above it first. So, you pick up the top eleven books and set them safely on your lap (the spare peg). Now you can slide the bottom book to the right side of the desk. Finally, you take the eleven books from your lap and place them back onto the bottom book. The act of moving the eleven books from the desk to your lap is exactly the same problem as moving the twelve books—it’s just smaller. You repeat this until you are holding just one book, which you can easily move.


## Definition

The Tower of Hanoi is a puzzle where you move a stack of disks between three pegs one at a time, never placing a larger disk on a smaller one; its solution works by moving the top n-1 disks to a spare peg, moving the largest disk to the goal, and then moving the n-1 disks from the spare peg to the goal, with the minimum number of moves required being two raised to the power of n minus one.


## How it connects

This concept introduces Recursion (solving a problem by applying the same solution to smaller versions of itself) and Complexity (how the amount of work or memory grows as the input size increases). It also connects to Depth-First Search with Backtracking (exploring one path as far as possible before stepping back, similar to how you must return from smaller sub-problems) and Stack Memory Behaviour (the system’s way of keeping track of these nested steps).


## The mathematics

The mathematics behind the Tower of Hanoi is discrete mathematics — the study of counting, arrangements, and structures made of separate pieces, as opposed to continuous smooth changes. Here, the problem is about counting moves, so it draws on discrete mathematics, specifically recurrence relations. A recurrence relation is a rule that tells you how to get the answer for n from the answer for n-1. For the Tower of Hanoi, the rule is: to move n disks, you first move n-1 disks (that takes some number of moves), then move the largest disk (that takes one move), then move n-1 disks again (that takes the same number of moves again). So the total number of moves for n disks is twice the number of moves for n-1 disks, plus one. That is the recurrence. To use it, you need a starting point: moving 1 disk takes 1 move (just pick it up and put it down). Then you can build up: 2 disks take 2 times 1 plus 1 equals 3 moves, 3 disks take 2 times 3 plus 1 equals 7 moves, and so on. The pattern is that the number of moves doubles each time you add a disk, so after n disks, the count is 2^n - 1. This is called exponential growth. The number of moves grows very fast: with 10 disks, it is already over a thousand; with 64, it would take billions of years, which is the origin of the legend that the world will end when monks finish moving 64 disks. The exponential cost is the key lesson: even though the recursive solution is short and elegant, it is not efficient in terms of the number of moves.

Let M(n) be the minimum number of moves for n disks. The recurrence is: M(n) = 2 × M(n-1) + 1, with the base case M(1) = 1. Solving this recurrence gives the closed form: M(n) = 2^n - 1.


## A worked example

```
We want to count the minimum number of moves needed to solve the Tower of Hanoi for n disks. We'll start with n = 1 and build up to n = 4 by hand.

Step 1: n = 1: moves = 1 (just move the single disk from start to goal)   # Base case: with 1 disk, it takes 1 move.
Step 2: n = 2: moves = 2 × 1 + 1 = 3   # Move 1 disk to the spare, move the largest to the goal (1 move), then move the 1 disk from spare to goal (1 move).
Step 3: n = 3: moves = 2 × 3 + 1 = 7   # Move 2 disks to the spare (3 moves), move the largest (1 move), then move 2 disks back (3 moves). Total 7.
Step 4: n = 4: moves = 2 × 7 + 1 = 15   # The pattern continues: double the previous count and add one.

Result: The minimum number of moves for n disks is 2^n - 1. For n = 4, that is 15 moves.
```


## From scratch, in Python

```python
# We'll build a recursive function step by step.
# First, let's introduce the building block: a function.
# A function is a named block of code you can 'call' (run) whenever you need it.
# Example:
# def greet(name):
#     return "Hello, " + name

# Now, the Tower of Hanoi.
# The function takes three pegs (just names like 'A', 'B', 'C') and n disks.

def hanoi(n, start, spare, goal):
    """Print the moves to move n disks from start to goal using spare."""
    if n == 1:
        # Base case: one disk, just move it.
        print(f"Move disk 1 from {start} to {goal}")
        return
    # Step 1: move n-1 disks from start to spare (using goal as the spare)
    hanoi(n-1, start, goal, spare)
    # Step 2: move the largest disk from start to goal
    print(f"Move disk {n} from {start} to {goal}")
    # Step 3: move the n-1 disks from spare to goal (using start as the spare)
    hanoi(n-1, spare, start, goal)

# To see it work with 3 disks:
hanoi(3, "A", "B", "C")
```


## What the code does

The function `hanoi` takes four parameters: `n` (the number of disks), `start` (the peg they start on), `spare` (the auxiliary peg), and `goal` (the target peg). The first line inside the function is the base case: if there is only one disk, it prints that the disk moves from start to goal, and the function returns (stops). This prevents infinite recursion. If there is more than one disk, the function does three things in order: first, it calls itself with `n-1` disks, moving them from start to spare (so the largest disk is free). That call will itself print all the necessary moves for the smaller stack. Second, it prints the move for the largest disk. Third, it calls itself again with `n-1` disks, now moving them from spare to goal. Because each recursive call works on a smaller number of disks, the recursion eventually hits the base case and terminates. The `print` statements show the sequence of moves. Running the function with three disks prints seven lines, which is the expected 2^3 - 1 = 7 moves.


## Common misconceptions

**The recursive solution is the fastest way to solve it** — I can make a recursive function that runs quickly, so it must be efficient.

Efficiency is about how the time needed grows as the input gets bigger. The recursive solution does exactly the minimum number of moves, which is 2^n - 1, and that is exponential. For any n beyond about 30, it is astronomically slow, even though the code is short. In fact: The recursive solution is the correct and canonical solution, but it is inherently exponential. Elegance does not mean efficiency — this is a core lesson.

**I need to track all disk movements manually** — To write a program, I have to simulate every disk move step by step.

That is possible but tedious and error-prone. The beauty of recursion is that you only need to think about the biggest disk, and let the recursion handle the smaller ones. In fact: The recursive function only handles one disk at a time, but the structure of the calls automatically produces the correct sequence for all disks.

**Base case is optional** — I can write a recursive function without a base case; it will just run until it's done.

Without a base case, the recursion never stops — it keeps calling itself with decreasing n into negative numbers, and eventually the program crashes with a recursion error. In fact: Every recursion needs a base case that stops the descent. In this puzzle, the base case is when n = 1.

**The problem is NP-hard** — The Tower of Hanoi sounds like an optimization puzzle, so it must be NP-hard.

NP-hardness is about decision or optimization problems with certain complexity properties. The Tower of Hanoi has a known optimal solution (2^n - 1 moves), so it's not NP-hard; it's just exponentially many steps. In fact: The Tower of Hanoi is not NP-hard; it has a simple closed-form solution, but the number of steps is exponential in n.

**You can solve it with three pegs in fewer moves by being clever** — Maybe there's a trick that reduces the number of moves below 2^n - 1.

The 2^n - 1 bound is proven to be optimal. Any solution must move the largest disk once, and the n-1 smaller disks must all move at least twice (once off, once on), and you can't do better than the recursive schema. In fact: The recursive strategy is already optimal; no shorter solution exists.


## In short

The Tower of Hanoi teaches you recursion: solve a problem by solving a smaller version of itself. The solution is: move n-1 disks aside, move the largest disk, then move the n-1 disks back. The recurrence M(n) = 2*M(n-1) + 1 gives the minimum moves, which is 2^n - 1. This is the canonical example of exponential complexity — short and elegant code can still be astronomically slow. Understanding this prepares you for depth-first search, recursion in AI, and the importance of complexity analysis.


## Where this is used

The Tower of Hanoi is not a machine-learning algorithm, and you will not find a library function to solve it in NumPy or PyTorch. It appears only as a teaching example in computer science courses, a benchmark for recursion, and an analogy for how recursion and exponential complexity work. Its real value is in building your intuition for recursion, which is everywhere in AI systems. For example, depth-first search, a core technique for exploring game trees and planning paths, is naturally recursive: to search a branch, you search its sub-branches, and so on until you hit a leaf. In agentic systems, an agent deciding which tool to call next can be seen as searching a tree of possible actions, each choice leading to further choices — the same recursive structure. In large language models, recursive structure appears in the way sentences are parsed into clauses, or in the way a model might plan a sequence of steps, each step depending on the previous ones. Additionally, the exponential cost of the Tower of Hanoi is a stark warning about complexity: even an elegant, short solution can be too slow for large inputs. This transfers directly to AI, where an algorithm that seems simple in code might be infeasible in practice because of exponential blow-up. For a developer, understanding this means respecting the difference between a correct recursion and an efficient one — and sometimes using memoisation or dynamic programming (turning exponential into polynomial) as your library notes on recursion remind you. When you build software that involves recursion, you write plain Python functions like the one above, and the recursion depth translates into stack memory; too deep a recursion will crash your program. Libraries won't save you from that — it's a language and design feature. So, while the Tower of Hanoi itself has no direct production use, it teaches you the mental model you need for DFS, for game AI, for planning, and for understanding why some recursive solutions are too slow to run.


---

Read this on the web: https://basavapurushottam.com/learn-ai/tower-of-hanoi
