Hanoi towers function code#

Then we have that all n disks start on tower (rod) 0 and should end in tower (rod) 2. If we number the towers (rods) 0, 1, and 2. This means that the problem starts with n disks. Move the smaller problem of 2 disks from second tower (rod) to last tower (rod).įirst understand that there can be any number of disks in an instance of Tower of Hanoi.Move the big disk from first tower (rod) to last tower (rod).Move the smaller problem of 2 disks from first tower (rod) to second tower (rod).Then we can move disk 3 to the final destination.Īnd after that, we should move the smaller problem of the 2 disks on top fo disk 3. What do we need to make happen if we should move disk 3 from first tower (rod) to the last tower (rod)?Įxactly.

How can we break that down to a smaller problem? Step 3: Implement Tower of Hanoi with a recursive function

Hanoi towers function code#

It will make your code easy and straight forward. The example of Tower of Hanoi will show you the benefit. The above might not be a good example of how recursion helps you. Well, what did we gain from making the function recursive? Let’s first try to do in the iterative way. It can be a bit difficult to connect the definition of recursions to getting the sum of the integers 1 + 2+ 3 + … + (n – 1) + n. While that is a beautiful and perfect definition – there is still need to exemplify what that means.Ī simple example is to sum up the numbers from 1 to n. Recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. Step 2: Recall recursion and unleash the power of it Now do yourself a favor and try to think how you would solve that. The third rule says, that we cannot move disk 2 on top of disk 1. Say, in the above we have moved the disk 1 from the first to the second tower (rod).Īfter that move, we can move disk 2 or disk 1. The first two rules combined means that you can only take one top disk and move it.

You cannot place a bigger disk on top of a smaller disk.

You can only take the top disk and place on top of another tower (rod).

You can only move one disk at the time.

The goal is to move all the disks from on tower (rod) to another one with the following 3 rules.

The disk all have different sizes as pictured above. A basic setup of Tower of Hanoi with 3 disks and 3 towers (often called rods) Before we set the rules, let’s see how our universe looks like. Tower of Hanoi is a mathematical game, which has three rules. The other three parameters, namely, source, target and other, are of type char and specify a single character identification of the source, target and intermediate poles, respectively.Step 1: Understand the Tower of Hanoi challenge The parameter n disk of type int specifies the number of disks to be moved. The complete program that includes a recursive function hanoi is given below. Thus, the terminating condition for this problem is that the number of disks to be moved should be equal to zero. Note that the problem of moving n – 1 disks in steps l and 3 will actually be solved in terms of the smaller problem of moving n – 2 disks, which in turn will be solved in terms of the still smaller problems involving n – 3 disks and so on for as long as there is at least one disk to be moved. The second step is to decide the terminating condition.