I’ve always found this algorithm interesting, ever since I saw it in action back in university. I think it was among the first recursive functions we ever went over, albeit not a simple one to grasp, which is probably the reason why they wanted to teach it to us. Typically, the algorithm to move disks for the Towers of Hanoi is as follows:

public void Calculate(int n, int fromPole, int toPole, int intermediaryPole) { if (n == 1) { Move(fromPole, toPole); // This is the only place that does the actual move. } else { Calculate(n - 1, fromPole, intermediaryPole, toPole); // The first Calculate call in the recursion serves to expose the bottom-most disk. Calculate(1, fromPole, toPole, intermediaryPole); // The second call in the Calculate method serves to move the bottom-most disk to the desired pole. Calculate(n - 1, intermediaryPole, toPole, fromPole); // The last Calculate call in the recursion does exactly the same thing as the last two calls in this recursion did, except it repeats this process for the disks remaining in the intermediary pole. } }

Assume you call it as follows:

Calculate(numberOfDisksOnTheFirstPole, 0, 2, 1);

The initial conditions are that you have all of the disks on the first pole. You have three poles, and you want to move all disks from pole 0 to 2 via pole 1 as an intermediary pole. Assume 4 disks in total, so that the tower looks like this (each column represents a pole, and the disks are numbered):

1-- 2-- 3-- 4--

Calls then runs as follows (I like to show the flow of the the method through coalescing, recursive function calls because its visually much more understandable to me to project a recursive method this way, and this is a tool I use to trace through recursive methods in order to figure out how they work, and I suggest that you use the same tool to project recursive functions in order to analyze them for understandability for yourself):

Calculate(4, 0, 2, 1) { Calculate(3, 0, 1, 2) { Calculate(2, 0, 2, 1) { Calculate(1, 0, 1, 2) { Moves the disk from pole 0 to pole 1. 2-- 3-- 41- } Calculate(1, 0, 2, 1) { Moves the disk from pole 0 to pole 2. 3-- 412 } Calculate(1, 1, 2, 0) { Moves the disk from pole 1 to pole 2. 3-1 4-2 } } Calculate(1, 0, 1, 2) { Moves the disk from pole 0 to pole 1. --1 432 } Calculate(2, 2, 1, 0) { Calculate(1, 2, 0, 1) { Moves the disk from pole 2 to pole 0. 1-- 432 } Calculate(1, 2, 1, 0) { Moves the disk from pole 2 to pole 1. 12- 43- } Calculate(1, 0, 1, 2) { Moves the disk from pole 0 to pole 1. -1- -2- 43- } } }// The last set of calls up to here expose the bottom-most disk, meaning the first Calculate call in the recursion serves to expose the bottom-most disk.Calculate(1, 0, 2, 1) { Moves the disk from pole 0 to pole 2. -1- -2- -34 }// The second call in the Calculate method serves to move the bottom-most disk to the desired pole.Calculate(3, 1, 2, 0) { Calculate(2, 1, 0, 2) { Calculate(1, 1, 2, 0) { Moves the disk from pole 1 to pole 2. -21 -34 } Calculate(1, 1, 0, 2) { Moves the disk from pole 1 to pole 0. --1 234 } Calculate(1, 2, 0, 1) { Moves the disk from pole 2 to pole 0. 1-- 234 } } Calculate(1, 1, 2, 0) { Moves the disk from pole 1 to pole 2. 1-3 2-4 } Calculate(2, 0, 2, 1) { Calculate(1, 0, 1, 2) { Moves the disk from pole 0 to pole 1. --3 214 } Calculate(1, 0, 2, 1) { Moves the disk from pole 0 to pole 2. --2 --3 -14 } Calculate(1, 1, 2, 0) { Moves the disk from pole 1 to pole 2. --1 --2 --3 --4 } } }// The last Calculate call in the recursion does exactly the same thing as the last two calls in this recursion did, except it repeats this process for the disks remaining in the intermediary pole.}

Thank you so much. This is the best explanation of Towers of Hanoi on the internet. It shows ‘how the code actually works’ and most importantly ‘ which function calls whom. The concept of recursion is clear to me now. Thank you.