A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing


  • 4 years ago

(Tower of Hanoi algorithm) For this algorithm: Tower(n,start, finish, other) if n>0 then Tower(n-1, start, other, finish) println(‘move from ’ + start + ‘ to ’ + finish ) Tower(n-1, other, finish, start) end if Could someone explain to me how it works and give an example because I am especially confused by the fact that there are two recursive calls in the method? (I played the game online on purpose so I know how to play.)

  • This Question is Closed
  1. jagatuba
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Recursion is used because the steps in moving the disks from point A to point C is determined by the size of the disk being moved. Therefore, as each disk is moved the algorithm can be reused to determine where to move it. This is probably as simply as it can be stated. Perhaps someone else can explain it more plainly, but if you want a more detailed explanation, I found the one provided in Wikipedia to be pretty good: As in many mathematical puzzles, finding a solution is made easier by solving a slightly more general problem: how to move a tower of h (h=height) disks from a starting peg A (f=from) onto a destination peg C (t=to), B being the remaining third peg and assuming t≠f. First, observe that the problem is symmetric for permutations of the names of the pegs (symmetric group S3). If a solution is known moving from peg A to peg C, then, by renaming the pegs, the same solution can be used for every other choice of starting and destination peg. If there is only one disk (or even none at all), the problem is trivial. If h=1, then simply move the disk from peg A to peg C. If h>1, then somewhere along the sequence of moves, the largest disk must be moved from peg A to another peg, preferably to peg C. The only situation that allows this move is when all smaller h-1 disks are on peg B. Hence, first all h-1 smaller disks must go from A to B. Subsequently move the largest disk and finally move the h-1 smaller disks from peg B to peg C. The presence of the largest disk does not impede any move of the h-1 smaller disks and can temporarily be ignored. Now the problem is reduced to moving h-1 disks from one peg to another one, first from A to B and subsequently from B to C, but the same method can be used both times by renaming the pegs. The same strategy can be used to reduce the h-1 problem to h-2, h-3, and so on until only one disk is left. This is called recursion. This algorithm can be schematized as follows. Identify the disks in order of increasing size by the natural numbers from 0 up to but not including h. Hence disk 0 is the smallest one and disk h-1 the largest one. The following is a procedure for moving a tower of h disks from a peg A onto a peg C, with B being the remaining third peg: Step 1: If h>1 then first use this procedure to move the h-1 smaller disks from peg A to peg B. Step 2: Now the largest disk, i.e. disk h-1 can be moved from peg A to peg C. Step 3: If h>1 then again use this procedure to move the h-1 smaller disks from peg B to peg C. By means of mathematical induction, it is easily proven that the above procedure requires the minimal number of moves possible, and that the produced solution is the only one with this minimal number of moves. Using recurrence relations, the exact number of moves that this solution requires can be calculated by: \[2^{h}-1\]This result is obtained by noting that steps 1 and 3 take \[T _{h-1}\]moves, and step 2 takes one move, giving \[T _{h} = 2T _{h-1} + 1\](sorry, I've already forgotten how to make LaTeX print the equations on one line)

  2. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...


  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.