Understanding the Towers of Hanoi Recursion

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.
}

Alexandru

"To avoid criticism, say nothing, do nothing, be nothing." - Aristotle

"It is wise to direct your anger towards problems - not people; to focus your energies on answers - not excuses." - William Arthur Ward

"Science does not know its debt to imagination." - Ralph Waldo Emerson

"Money was never a big motivation for me, except as a way to keep score. The real excitement is playing the game." - Donald Trump

"All our dreams can come true, if we have the courage to pursue them." - Walt Disney

"Mitch flashes back to a basketball game held in the Brandeis University gymnasium in 1979. The team is doing well and chants, 'We're number one!' Morrie stands and shouts, 'What's wrong with being number two?' The students fall silent." - Tuesdays with Morrie

I'm not entirely sure what makes me successful in general programming or development, but to any newcomers to this blood-sport, my best guess would be that success in programming comes from some strange combination of interest, persistence, patience, instincts (for example, someone might tell you that something can't be done, or that it can't be done a certain way, but you just know that can't be true, or you look at a piece of code and know something doesn't seem right with it at first glance, but you can't quite put your finger on it until you think it through some more), fearlessness of tinkering, and an ability to take advice because you should be humble. Its okay to be wrong or to have a bad approach, realize it, and try to find a better one, and even better to be wrong and find a better approach to solve something than to have had a bad approach to begin with. I hope that whatever fragments of information I sprinkle across here help those who hit the same roadblocks.

One thought on “Understanding the Towers of Hanoi Recursion

  1. 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.

Leave a Reply

Your email address will not be published. Required fields are marked *