Recursion Basics: Base Case and Recursive Case

The Towers of Hanoi puzzle starts with a stack of disks of various sizes, piled on a base in order of decreasing size. The goal is to move the whole stack from one base to another. Only one disk can move at a time, and no disk may ever be placed on top of a smaller disk. A third base is available as a spare.

Many learners assume that a program solving this puzzle must keep track of every disk and every move at once, because the puzzle is made of many small physical steps. That belief feels natural, and it is the belief this article tests. The recursive solution turns out to need far less bookkeeping than the puzzle's detail suggests. Keep that expectation in mind as you work through the example below.

The diagram below follows the two-disk case from the prediction step. Each node is the state of the three stacks after one more move. Watch what changes at each step: only the top disk of one stack ever moves, and it always lands on a larger disk or on an empty stack. Stack 0 starts with the large disk underneath and the small disk on top. Stack 1 is the destination and Stack 2 is the spare.

Notice that the three moves form a pattern. The first and third moves are the same kind of job: moving a single small disk out of the way and then onto its final place. The middle move is the one that finally moves the bottom disk to the destination. This pattern is the seed of the recursive solution.

The key idea is to notice that the problem contains a smaller copy of itself. Suppose there are N disks on the source stack. The bottom disk must eventually travel from the source stack to the destination stack. Before that can happen, all of the other N minus 1 disks must be sitting on the spare stack, because the bottom disk cannot move while smaller disks are on top of it. After the bottom disk arrives at the destination, the N minus 1 disks must travel from the spare stack to the destination stack.

This gives a three-step pattern: move N minus 1 disks, move the bottom disk, then move N minus 1 disks again. Moving N minus 1 disks is the same kind of problem as moving N disks, only smaller. That is why recursion fits so well here: the problem is reduced to smaller problems of the same type.

In the tree, the top-level call has three children, and the two subproblems each expand into their own three-step pattern. The middle child is the single move of the largest disk. The structure is the same at every level, which is exactly what makes the recursive description short even though the list of moves is long.

The source expresses the solution as a subroutine that prints step-by-step instructions. It takes four parameters, and each one has a specific job. The first is the number of disks to move. The second is the source stack, the third is the destination stack, and the fourth is the spare stack. Stacks are identified by number: 0, 1, or 2.

The spare parameter is technically redundant, since it could be worked out from the other three stacks. The source keeps it anyway because it makes each call easier to read. To solve the top-level problem of moving N disks from Stack 0 to Stack 1, the subroutine is called as TowersOfHanoi(N,0,1,2). The source's own program calls the method with that name, so match that spelling when you read the source code.

The roles of the stacks are not fixed. The first subproblem moves disks from the source to the spare, and the second moves disks from the spare to the destination. So the subroutine must accept source, destination, and spare as inputs, and the roles of those three stacks change from one call to the next. A stack that is the destination in one call may be the spare in the next.

Every recursive method needs a stopping point, and here the stopping point is the case with only one disk. In that case the solution is trivial: the single disk moves in one step. The subroutine checks for this case first. If the number of disks is exactly one, it prints one move and does not call itself again. Otherwise it performs the three-step pattern. The one-disk case is the base case, and the three-step pattern is the recursive case.

The recursion works because each recursive call handles a smaller number of disks. Each step of the descent reduces the disk count by one, so the calls eventually reach the one-disk base case. The source states this directly: the recursion works because each recursive call involves a smaller number of disks, and the problem is trivial in the base case.

The following pseudocode captures the structure described above. It is an illustration generated for teaching purposes, following the base case and the three-step pattern from the source. The parameter order matches the roles the source gives to each stack.

The solution depends on a precondition: the number of disks must be positive. The source notes that violating this precondition produces infinite recursion. The reason is visible in the code. The only stopping check is whether disks equals 1. A call with zero disks never matches that check, so it always takes the recursive branch.

The lesson is that a recursive method is only correct when every call moves toward its base case. Here the recursion steps downward by one disk per call, so a starting value that is positive will reach 1, while a starting value of zero or below will skip past 1 forever. The positive-disk precondition is what guarantees that the base case is reachable.

Recursion makes the solution elegant, but it does not make the solution cheap. The number of moves needed for N disks is given by a simple formula. Each extra disk roughly doubles the work, so the count grows exponentially.

The source gives a story to illustrate this growth. Monks are said to move a stack of 64 disks, one disk per day, and the universe is said to end when they finish. The source also states that the algorithm runs in time Theta of 2 to the power n, where n is the number of disks. Because this grows so quickly, the problem can be solved in practice only for a small number of disks.