Algorithm Design: Recursive Algorithms

Recursive algorithms

Recursion is one of the most ubiquitous algorithmic concepts. Simply put, an algorithm is recursive if it calls itself.

The Towers of Hanoi puzzle consists of three pegs, which we label from left to right as 1, 2, and 3, and a number of disks of decreasing radius, each with a hole in the center. The disks are initially stacked on the left peg (peg 1) so that smaller disks are on top of larger ones. The game is played by moving one disk at a time between pegs.

Where we can place smaller disks on top of larger ones, any disk may go onto an empty peg. The puzzle is solved when all of the disks have been moved from peg 1 to peg 3.

Note: Try our interactive puzzle to figure out how to move all disks from one peg to another. Click on a disk to remove it from the current peg and click on a different peg to move it there.

$\rule[0 pt]{1000 pt}{0.5 pt}\\$

Towers of Hanoi problem

Output a list of moves that solves the Towers of Hanoi.

Input: An integer $n$.

Output: A sequence of moves that solve the $n$-disk Towers of Hanoi puzzle. $\rule[0 pt]{1000 pt}{0.5 pt}\\$

Solving the puzzle with one disk is easy: move the disk to the right peg. The two-disk puzzle is not much harder: move the small disk to the middle peg, then the large disk to the right peg, then the small disk to the right peg to rest on top of the large disk.

The three-disk puzzle is somewhat harder, but the following sequence of seven moves solves it:

Now we’ll figure out how many steps are required to solve a four-disk puzzle. We cannot complete this game without moving the largest disk. However, in order to move the largest disk, we first have to move all the smaller disks to an empty peg. If we had four disks instead of three, then we would first have to move the top three to an empty peg (seven moves), then move the largest disk (one move), then again move the three disks from their temporary peg to rest on top of the largest disk (another seven moves). The whole procedure will take $7 + 1 + 7 = 15$ moves.

Generally, to move a stack of size $n$ from the left to the right peg, we first need to move a stack of size $n − 1$ from the left to the middle peg, and then from the middle peg to the right peg once we have moved the $n$-th disk to the right peg. To move a stack of size $n − 1$ from the middle to the right, we first need to move a stack of size $n−2$ from the middle to the left, then move the ($n − 1$)-th disk to the right, and then move the stack of size $n − 2$ from the left to the right peg, and so on.

At first glance, the Towers of Hanoi Problem looks difficult. However, the following recursive algorithm solves the Towers of Hanoi Problem with just nine lines!

---

 $HanoiTowers(n,fromPeg,toPeg)$:
 if $n=1$:
       output “Move disk from peg $fromPeg$ to peg $toPeg$”
       return
 $unusedPeg$ $\leftarrow$ $6$ − $fromPeg$ − $toPeg$
 $HanoiTowers(n-1,fromPeg,unusedPeg)$ ...