Alright, so everything was going smooth with this book I'm reading (Data Structures for Game Programmers) until I got to the chapter on recursion. The first problem the author wants you to figure out is solving x to the nth power recursively. Alright, simple enough. I figured that one out pretty quickly, and thought that the next problem couldn't be any harder than that...
Pseudo Code: (n = total blocks, s = start pole, d = dest pole, o = open pole)
Hanoi(n, s, d, o)
if(n > 0)
Hanoi(n-1, s, o d);
Print "Moving n from s to d."
Hanoi(n-1, o, d, s)
Example with calling Hanoi( 3, 1, 3, 2) prints out:
1 2 3
============
1 | | |
2 | | |
3 | | |
Step 1: Moving 1 from 1 to 3.
1 2 3
============
| | |
2 | | |
3 | | 1 |
Step 2: Moving 2 from 1 to 2.
1 2 3
============
| | |
| | |
3 | 2 | 1 |
Step 3: Moving 1 from 3 to 2.
1 2 3
============
| | |
| 1 | |
3 | 2 | |
Step 4: Moving 3 from 1 to 3.
1 2 3
============
| | |
| 1 | |
| 2 | 3 |
Step 5: Moving 1 from 2 to 1.
1 2 3
============
| | |
| | |
1 | 2 | 3 |
Step 6: Moving 2 from 2 to 3.
1 2 3
============
| | |
| | 2 |
1 | | 3 |
Step 7: Moving 1 from 1 to 3.
1 2 3
============
| | 1 |
| | 2 |
| | 3 |
( 2^n - 1 moves)
35 minutes later, I'm still trying to figure out why the tower of hanoi recursive algorithm works. Basically, it looks like this:
void Hanoi(int numberOfBlocks, int startPole, int destPole, int openPole)
{
if( numberOfBlocks > 0 )
{
// openPole and destPole are swapped
Hanoi(numberOfBlocks - 1, startPole, openPole, destPole);
cout << "Moving " << n << " from " << startPole;
cout << " to " << destPole << endl;
// openPole and startPole are swapped
Hanoi(numberOfBlocks - 1, openPole, destPole, startPole);
}
}
Alright, so I'll be passing in the total number of blocks to move, the starting pole those blocks are on, the final pole where they should end up, and the open pole. Lets say I have three blocks total, located on pole #1. I have a total of three poles, with #3 being the destination and #2 being the open pole. I want to move all 3 blocks to #3.
So I call the Hanoi function like this:
In the function, the if statement checks if numberOfBlocks is > 0, which it is, and then calls Hanoi again with numberOfBlocks - 1. The if statement gets checked again, and now numberOfBlocks = 2, so Hanoi is called again with numberOfBlocks - 1, and the if statement gets checked again seeing that numberOfBlocks now equals 1. Pretty simple recursion at this point. After the next call the function will start returning because the if statement will be false, and then cout will be called for the results of the second recursion (where n = 1). Then Hanoi is called again, until n = 0.
Original call: ( 3, 1, 3, 2 ); // n, s, d, o
1. (2, 1, 2, 3 ); // n, s, o, d
2. (1, 1, 2, 3 );
3. (0, 1, 2, 3 ); // if statement fails, function returns back to step 2
------
And this is where I'm getting lost. After the third call's if statement fails, it returns back to step 2, where the first message is printed and Hanoi is called again. This time, the openPole and startPole values are swapped, so the call should look like this:
4. ( 1 (?), 2, 3, 1) // n, o, d, s
At this point, what is the value of n that is passed into the function? At step 2, n = 2, so I'm assuming that the ? in step 4 should be 2-1, or just 1. Which starts the entire thing again because the if statement is true. So, after each time the second hanoi function is called, it goes through the first few steps again.
At this point, short of writing out /every/ step on a few sheets of paper, I don't see how it actually moves the correct pieces in the correct order. I'm really close to just pulling out a pad of paper and writing down each and every function call and the values involved, but I'm hoping someone who already understands how this works can help me out a bit. I understand how recursion works, but I don't understand how and why this algorithm does what it does.
