Ruby Program for Tower of Hanoi with Output and Explanation

A Ruby program for Tower of Hanoi uses a recursive method like def hanoi(n, from, to, aux) that moves disks between rods by calling itself until all disks are moved.

Examples

Input3 disks

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 disk

OutputMove disk 1 from A to C

Input0 disks

Output

How to Think About It

To solve Tower of Hanoi, think about moving the top n-1 disks to the auxiliary rod first, then move the largest disk to the target rod, and finally move the n-1 disks from the auxiliary rod to the target rod. This repeats recursively until no disks remain to move.

Algorithm

1

If there are no disks to move, return.

2

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

3

Move the nth disk from the source rod to the target rod.

4

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

Code

ruby

def hanoi(n, from, to, aux)
  return if n == 0
  hanoi(n - 1, from, aux, to)
  puts "Move disk #{n} from #{from} to #{to}"
  hanoi(n - 1, aux, to, from)
end

hanoi(3, '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 moving 2 disks from rod A to rod C using rod B as auxiliary.

1

Move 1 disk from A to B

Call hanoi(1, 'A', 'B', 'C') which prints: Move disk 1 from A to B

2

Move disk 2 from A to C

Print: Move disk 2 from A to C

3

Move 1 disk from B to C

Call hanoi(1, 'B', 'C', 'A') which prints: Move disk 1 from B to C

Call	Action
hanoi(2, A, C, B)	Move 1 disk from A to B
Move disk 2 from A to C	Print move
hanoi(1, B, C, A)	Move 1 disk from B to C

Why This Works

Step 1: Base Case

The code stops recursion when n == 0, meaning no disks to move.

Step 2: Recursive Calls

It moves n-1 disks to the auxiliary rod first, then moves the largest disk.

Step 3: Final Move

It moves the n-1 disks from auxiliary to target rod, completing the process.

Alternative Approaches

Iterative approach using stack

ruby

def hanoi_iterative(n)
  total_moves = 2**n - 1
  rods = { 'A' => (1..n).to_a.reverse, 'B' => [], 'C' => [] }
  from, to, aux = 'A', 'C', 'B'
  if n.even?
    to, aux = aux, to
  end
  (1..total_moves).each do |move|
    case move % 3
    when 1
      move_disk(rods, from, to)
    when 2
      move_disk(rods, from, aux)
    when 0
      move_disk(rods, aux, to)
    end
  end
end

def move_disk(rods, src, dst)
  if rods[src].empty?
    disk = rods[dst].pop
    rods[src].push(disk)
    puts "Move disk #{disk} from #{dst} to #{src}"
  elsif rods[dst].empty? || rods[src].last < rods[dst].last
    disk = rods[src].pop
    rods[dst].push(disk)
    puts "Move disk #{disk} from #{src} to #{dst}"
  else
    disk = rods[dst].pop
    rods[src].push(disk)
    puts "Move disk #{disk} from #{dst} to #{src}"
  end
end

hanoi_iterative(3)

This uses a loop and stacks to simulate moves without recursion but is more complex to understand.

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 is linear in the number of disks.

Which Approach is Fastest?

Both recursive and iterative methods perform the same number of moves; recursion is simpler to write and understand.

Approach	Time	Space	Best For
Recursive	O(2^n)	O(n)	Simplicity and clarity
Iterative	O(2^n)	O(n)	Avoiding recursion stack, complex logic