Learn recursion with Tower of Hanoi game

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

• Only one disk can be moved at a time.
• Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
• No larger disk may be placed on top of a smaller disk.

hanoy.rb

def hanoi(number, origin, auxiliar, destination)
  unless number == 0
    hanoi(number - 1, origin, destination, auxiliar)
    puts "Moved disc from #{origin} to #{destination}"
    hanoi(number - 1, auxiliar, origin, destination)
  end
end

hanoi(4, 'A', 'B', 'C')

Tower of Hanoi

A Hanoi Tower looks like this:

• number (number of disks)
• origin (A)
• auxiliar (B)
• destination (C)

To make this example easier to understand, let's pretend our Hanoi Tower has 4 disks, and columns A, B, C.

 Our algorithm

The idea is to write a function that calls itself until the puzzle is solved.

 But how?

First, determine when to stop the function execution. It must stop when all the disks has been moved to the column C. Our program continues executing unless the disks is equal to zero. Code:

unless number == 0

Our next mission is to actually figure out the puzzle (moving all the disks from "A" to "C").

Second, we will have to decrement the amount of disks when calling hanoi and pass along the origin, destination and auxiliar. Code:

hanoi(number - 1, origin, destination, auxiliar)

Basically, we are calling the same function (hanoi) but using new arguments, allowing us to solve the puzzle.

Third, we also want to print whenever the disks are moving from one place to another. Code:

puts "Moved disc from #{origin} to #{destination}"

Finally, we will call hanoi again because we want to move the disks. Code:

hanoi(number - 1, auxiliar, origin, destination)

Notice, the arguments are the same but in different order, again allowing us to solve the puzzle.

Final thoughts

I do not want you to understand the math behind the Hanoi Tower algorithm, just want you to realize that calling function hanoi in the same function hanoi is recursion.

It is important to understand that a recursive function needs a mechanism to stop executing, otherwise it will run forever or in the worst case it will cause errors.

Maybe you noticed our hanoi function did not mutated objects because it calls itself with new arguments rather than using existing objects.