CODEWITHSUNDEEP
crecursion
Amir David
Amir David

Reputation: 33

I don't understand Hanoi algorithm

Let's be honest: I've been doing good in programming since the beginning of the year (high school senior high school) until the day we finally saw recursion. I don't understand the recursive code of Hanoi Towers: the specific point in it that i don't seem to get is the switch between the destination tower and origin and vice versa:

I basically understand what recursion is, and what a stack is, but I don't understand why the order of the towers is changed.

Your help will be greatly appreciated. Thank you. //N number of pieces

    private void Déplacer(short N, string o, string i, string d)
    {
        if (N == 1)
        {
            MessageBox.Show("Move " + o + "to " + d);
            lstUn.Items.Add((lstUn.Items.Count + 1).ToString() + "-" + "Move " + o + " vers " + d);
            return;
        }


        else
        { 
        //Switch d and i
            Déplacer((short)(N - 1), o, d, i);
            lstUn.Items.Add((lstUn.Items.Count + 1).ToString() + "-" + "Déplace " + o + " vers " + d);
            MessageBox.Show("Déplace " + o + " vers " + d); //1 vers 3
            Déplacer((short)(N - 1), i, o, d);

        }

Upvotes: 3

Views: 938

Answers (3)

ShenTianWen
ShenTianWen

Reputation: 51

The order of the towers is changed because the two recursive steps have different purposes. For one of them, the purpose is "move entire stack from tower A to tower C" (goal #1). For the other, the purpose is "move the bottom ring from tower A to tower C by putting all of the other rings on tower B" (goal #2).

It's probably easiest to understand if you look at an example with 3 rings. Initially we have:

A (3)(2)(1)
B
C

We want to move the rings from A to C, but to do that we first need to put the bottom ring on C. Thus, we start with goal #2. In goal #2, we need to move all of the other rings onto B, thus when stepping into it we get goal #1 but with the destination tower changed to B. Once done, we get:

A
B (2)(1)
C (3)

Now We have goal #1 from B to C. But to do this, we first have goal #2 from B to C (which is essentially goal #1 from B to A). So, basically, the destination tower changes because with each recursive step we're switching between goal #1 and goal #2.

Upvotes: 3

Ofir
Ofir

Reputation: 8372

A great explanation for the algorithm can be found in http://en.wikipedia.org/wiki/Tower_of_Hanoi#Recursive_solution

Notice how the code is almost a line to line implementation of this algorithm

Upvotes: 2

Jonathan Leffler
Jonathan Leffler

Reputation: 755016

Under the rules of the Tower of Hanoi, you can never put a bigger disk on top of a smaller one.

Imagine three towers, with tower 1 have three disks on it. To move the three disks to tower 3, you need to be able to move the biggest disk from tower 1 to tower 3; that means you have to move the two smaller disks from tower 1 to tower 2. How do you move the two disks from tower 1 to tower 2? Well, you need to move disk 1 to tower 3; then you can move disk 2 to tower 2; then you can move disk 1 from tower 3 to tower 2. Now you can move disk 3 to tower 3; and you need to move the two disks from tower 2 to tower 3 - which means you move disk 1 to tower 1; then disk 2 to tower 3; and finally disk 1 to tower 3, completing the process.

And that is the essence of the algorithm. Each time you need to move some number of disks from one tower to another, you recurse.

A consequence of the rules is that the smallest disk is moved every other step.

Upvotes: 2

Related Questions