If you've gone through the tutorial on recursion, then you're ready to see another problem where recursing multiple times really helps. It's called the Towers of Hanoi. You are given a set of three pegs and
disks, with each disk a different size. Let's name the pegs A, B, and C, and let's number the disks from 1, the smallest disk, to , the largest disk. At the outset, all disks are on peg A, in order of decreasing size from bottom to top, so that disk is on the bottom and disk 1 is on the top. Here's what the Towers of Hanoi looks like for disks:
The goal is to move all
disks from peg A to peg B:
Sounds easy, right? It's not quite so simple, because you have to obey two rules:
- You may move only one disk at a time.
- No disk may ever rest atop a smaller disk. For example, if disk 3 is on a peg, then all disks below disk 3 must have numbers greater than 3.
You might think that this problem is not terribly important. Au contraire! Legend has it that somewhere in Asia (Tibet, Vietnam, India—pick which legend on the Internet you like), monks are solving this problem with a set of 64 disks, and—so the story goes—the monks believe that once they finish moving all 64 disks from peg A to peg B according to the two rules, the world will end. If the monks are correct, should we be panicking in the streets?
First, let's see how to solve the problem recursively. We'll start with a really easy case: one disk, that is,
. The case of will be our base case. You can always move disk 1 from peg A to peg B, because you know that any disks below it must be larger. And there's nothing special about pegs A and B. You can move disk 1 from peg B to peg C if you like, or from peg C to peg A, or from any peg to any peg. Solving the Towers of Hanoi problem with one disk is trivial, and it requires moving only the one disk one time.
How about two disks? How do you solve the problem when
? You can do it in three steps. Here's what it looks like at the start:
First, move disk 1 from peg A to peg C:
Notice that we're using peg C as a spare peg, a place to put disk 1 so that we can get at disk 2. Now that disk 2—the bottommost disk—is exposed, move it to peg B:
Finally, move disk 1 from peg C to peg B:
This solution takes three steps, and once again there's nothing special about moving the two disks from peg A to peg B. You can move them from peg B to peg C by using peg A as the spare peg: move disk 1 from peg B to peg A, then move disk 2 from peg B to peg C, and finish by moving disk 1 from peg A to peg C. Do you agree that you can move disks 1 and 2 from any peg to any peg in three steps? (Say "yes.")
Want to join the conversation?
- how do you this?(14 votes)
- You will need to start at the bottom because you can not put a ring underneath a ring that is already there.(3 votes)
- what does this have to do with computer science?(4 votes)
- this is setup for the problem. The computer science part is the algorithms that you can use to solve this problem, and other similar types of problems. Continue on to the next three parts of this section for all the details. The short answer is: an exercise in recursive thinking, and some practice in coding recursively.(8 votes)
- how can i solve the question without using recursion.(5 votes)
- I would guess just by using if else logic that goes through all possible moves while still complying with the two rules.(4 votes)
- If I used Recursion to solve the tower of Hanoi Problem time complexity is O(2^n) and if i solve this problem without using recursion ,what is the time complecity?(5 votes)
- Formulate the recurrence and derive the closed form solution for Triple Tower of Hanoi problem. A triple tower of Hanoi is a regular tower of Hanoi with three pegs, but each peg has three equal sized disks. You can move at most one disk at a time, and you can only put one disk on another if the disk you are putting is smaller or equal to the disk you are putting on to. Can any one solve this problem??(3 votes)
- Closed form solution for what ?
If you want the closed form solution for number of moves to solve the Tower of Hanoi problem then check out:
- easy, just move everything to the far-right peg and then put the biggest to smallest in the middle one.(2 votes)
- How can we solve this solution without recursion?(2 votes)
- It is possible to generate a simple rule for which disk to move, given any intermediate state in a solution, and to apply this rule 2^(n+1) - 1 times iteratively.(3 votes)
- Why is it the goal stated here is to move all the discs to the 2nd tower, when every other resource I've seen on this game states that the goal is to get them to the 3rd tower?(2 votes)
- Moving discs from tower 1 to tower 3, is equivalent to moving discs from tower 1 to tower 2. One could just swap the labels of tower 2 and tower 3 to prove that.
The labels that matter for this problem are:
-current peg (with the discs on it)
-the remaining peg
Thinking in terms of current, target and remaining pegs will help to understand how to approach the problem recursively.(2 votes)