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); } }

Hanoi( 3, 1, 3, 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.