Master the Tower of Hanoi in Go: Step-by-Step Recursive Implementation

In this article we revisit the classic Tower of Hanoi puzzle (also called the Hanota game) and show how to implement it in Go.

Game Origin

The problem is attributed to French mathematician Edouard Lucas and is linked to a legend about a temple in Benares where monks move 64 golden disks according to simple rules.

1 disk requires 2¹‑1 moves 2 disks require 2²‑1 moves 3 disks require 2³‑1 moves … n disks require 2ⁿ‑1 moves

If the legend were true, moving all disks at one move per second would take 584.9 billion years.

Game Rules Analysis

The puzzle uses three pegs (A, B, C) and N ordered disks, largest at the bottom. Only one disk may be moved at a time, and a larger disk may never be placed on top of a smaller one.

Move only one disk per step

Never place a larger disk on a smaller one

Initial and goal states are illustrated below:

Goal: transfer all disks from one peg to another while preserving order.

Implementation Idea

Think of the whole set of disks as a single entity.

To move the largest disk, first clear it by moving the top N‑1 disks to the auxiliary peg.

Move the largest disk to the target peg.

Finally move the N‑1 disks from the auxiliary peg onto the target peg.

Step 1: Move N‑1 disks from A to B

Because the final goal is to move all disks from A to C while keeping order, the N‑1 smaller disks must be placed on the auxiliary peg B.

Step 2: Move the largest disk from A to C

This is a single move.

Step 3: Move the N‑1 disks from B to C

The process repeats recursively: treat the N‑1 disks as a new puzzle.

Third step can be expressed as: Let K = N‑1. 1. Move K‑1 disks from B to A. 2. Move disk K from B to C. 3. Move K‑1 disks from A to C.

Repeat these steps until only the smallest disk remains, then move it directly to C.

Auxiliary Peg

The auxiliary peg is the one that temporarily holds the N‑1 disks while the largest disk moves.

Moving from A to B uses C as auxiliary. Moving from A to C uses B as auxiliary. Moving from B to C uses A as auxiliary.

Go Implementation

The algorithm maps naturally to a recursive function. Two essential elements are the recursive formula and the base case (one disk).

package main

import "fmt"

// Record the number of game steps
var count int = 0

func main() {
    beadNum := 5 // initial number of beads
    fmt.Printf("This is a Hannukah game with %d beads 
\r", beadNum)
    hanoi(beadNum, "A", "B", "C")
    fmt.Printf("Game over: %d steps spent in total 
\r", count)
}

// Recursive Hanoi function
func hanoi(beadNum int, pillarA string, pillarB string, pillarC string) {
    if beadNum == 1 {
        // Move single bead from A to C
        move(beadNum, pillarA, pillarC)
    } else {
        // Move N-1 beads from A to B (C as auxiliary)
        hanoi(beadNum-1, pillarA, pillarC, pillarB)
        // Move the largest bead from A to C
        move(beadNum, pillarA, pillarC)
        // Move the remaining N-1 beads from B to C (A as auxiliary)
        hanoi(beadNum-1, pillarB, pillarA, pillarC)
    }
}

// Helper to print a move and count steps
func move(beadNum int, pillarFrom string, pillarTo string) {
    count += 1
    fmt.Printf("Step %d: bead of %d from %s move to %s 
\r", count, beadNum, pillarFrom, pillarTo)
}

This code prints each move and the total number of steps required to solve the puzzle for any given number of disks.