Go Program for Tower of Hanoi with Output and Explanation

A Go program for Tower of Hanoi uses a recursive function like func towerOfHanoi(n int, from, to, aux string) to move disks between rods and prints each move.

Examples

Input3

OutputMove disk 1 from A to C Move disk 2 from A to B Move disk 1 from C to B Move disk 3 from A to C Move disk 1 from B to A Move disk 2 from B to C Move disk 1 from A to C

Input1

OutputMove disk 1 from A to C

Input0

Output

How to Think About It

To solve Tower of Hanoi, think about moving n disks from one rod to another using a helper rod. Move n-1 disks to the helper rod, then move the largest disk to the target rod, and finally move the n-1 disks from the helper rod to the target rod. This repeats until no disks remain.

Algorithm

1

If number of disks is 0, return (no moves).

2

Move n-1 disks from source rod to auxiliary rod using target rod.

3

Move the nth disk from source rod to target rod.

4

Move n-1 disks from auxiliary rod to target rod using source rod.

Code

go

package main

import "fmt"

func towerOfHanoi(n int, from, to, aux string) {
    if n == 0 {
        return
    }
    towerOfHanoi(n-1, from, aux, to)
    fmt.Printf("Move disk %d from %s to %s\n", n, from, to)
    towerOfHanoi(n-1, aux, to, from)
}

func main() {
    n := 3
    towerOfHanoi(n, "A", "C", "B")
}

Output

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

Dry Run

Let's trace the Tower of Hanoi program with 3 disks moving from rod A to rod C using rod B.

1

Move 2 disks from A to B using C

Call towerOfHanoi(2, A, B, C)

2

Move 1 disk from A to C using B

Call towerOfHanoi(1, A, C, B)

3

Move disk 1 from A to C

Print: Move disk 1 from A to C

4

Move 0 disks from B to C using A

Call towerOfHanoi(0, B, C, A) - returns immediately

5

Move disk 2 from A to B

Print: Move disk 2 from A to B

6

Move 1 disk from C to B using A

Call towerOfHanoi(1, C, B, A)

7

Move disk 1 from C to B

Print: Move disk 1 from C to B

8

Move disk 3 from A to C

Print: Move disk 3 from A to C

9

Move 2 disks from B to C using A

Call towerOfHanoi(2, B, C, A)

10

Move 1 disk from B to A using C

Call towerOfHanoi(1, B, A, C)

11

Move disk 1 from B to A

Print: Move disk 1 from B to A

12

Move 0 disks from C to A using B

Call towerOfHanoi(0, C, A, B) - returns immediately

13

Move disk 2 from B to C

Print: Move disk 2 from B to C

14

Move 1 disk from A to C using B

Call towerOfHanoi(1, A, C, B)

15

Move disk 1 from A to C

Print: Move disk 1 from A to C

Step	Action
1	Move 2 disks A->B using C
3	Move disk 1 A->C
5	Move disk 2 A->B
7	Move disk 1 C->B
8	Move disk 3 A->C
11	Move disk 1 B->A
13	Move disk 2 B->C
15	Move disk 1 A->C

Why This Works

Step 1: Recursive Breakdown

The problem breaks down into moving smaller stacks of disks recursively using towerOfHanoi calls.

Step 2: Base Case

When n == 0, no moves are needed, so the function returns immediately.

Step 3: Moving Largest Disk

After moving smaller disks out of the way, the largest disk moves directly from source to target rod.

Step 4: Completing the Move

Finally, the smaller disks move from auxiliary rod to target rod, completing the transfer.

Alternative Approaches

Iterative Approach Using Stack

go

package main

import (
	"fmt"
)

type Move struct {
	disk int
	from string
	to   string
}

func towerOfHanoiIterative(n int, from, to, aux string) {
	var stack []struct{
		n    int
		from string
		to   string
		aux  string
		state int
	}

	stack = append(stack, struct{
		n    int
		from string
		to   string
		aux  string
		state int
	}{n, from, to, aux, 0})

	for len(stack) > 0 {
		frame := &stack[len(stack)-1]
		switch frame.state {
		case 0:
			if frame.n == 0 {
				stack = stack[:len(stack)-1]
				continue
			}
			frame.state = 1
			stack = append(stack, struct{
				n    int
				from string
				to   string
				aux  string
				state int
			}{frame.n - 1, frame.from, frame.aux, frame.to, 0})
		case 1:
			fmt.Printf("Move disk %d from %s to %s\n", frame.n, frame.from, frame.to)
			frame.state = 2
			stack = append(stack, struct{
				n    int
				from string
				to   string
				aux  string
				state int
			}{frame.n - 1, frame.aux, frame.to, frame.from, 0})
		case 2:
			stack = stack[:len(stack)-1]
		}
	}
}

func main() {
	towerOfHanoiIterative(3, "A", "C", "B")
}

This iterative method uses a manual stack to simulate recursion, which can be harder to read but avoids function call overhead.

Complexity: O(2^n) time, O(n) space

Time Complexity

The algorithm makes 2^n - 1 moves, so time grows exponentially with the number of disks.

Space Complexity

The recursion stack depth is at most n, so space complexity is O(n).

Which Approach is Fastest?

Recursive approach is simpler and clear; iterative approach avoids recursion overhead but is more complex.

Approach	Time	Space	Best For
Recursive	O(2^n)	O(n)	Simplicity and clarity
Iterative with Stack	O(2^n)	O(n)	Avoiding recursion overhead