Tower of Hanoi Recursive Algorithm

Question

Although I have no problem whatsoever understanding recursion  I can t seem to wrap my head around the recursive solution to the Tower of Hanoi problem   Here is the code from Wikipedia   procedure Hanoi n  integer  source  dest  by  char   Begin     if  n 1  then         writeln  Move the plate from    source    to    dest      else begin         Hanoi n-1  source  by  dest           writeln  Move the plate from    source    to    dest           Hanoi n-1  by  dest  source       end  End   I understand the base case and the concept of breaking the problem into smaller pieces until you are able to move a single disk   However  I can t figure out how the two recursive calls in the non-base case work together   Perhaps someone can help me out   Thanks

User · Answer

There s a good explanation of the recursive Hanoi implementation at http   www cs cmu edu  cburch survey recurse hanoiimpl html   Summary is  if you want to move the bottom plate from stick A to stick B  you first have to move all the smaller plates on top of it from A to C  The second recursive call is then to move the plates you moved to C back onto B after your base case moved the single large plate from A to B

User · Answer

There are three towers namely source tower  destination tower and helper tower  The source tower has all the disks and your target is to move all the disks to the destination tower and make sure in doing so  you never put a larger disk on top of a smaller disk  We can solve this problem using recursion in the steps below   We have n numbers of disks on source tower  Base case  n 1   If there is only one disk in source tower  move it to destination tower    Recursive case  n  1    Move the top n-1 disks from from source tower to helper tower  Move the only remaining  the nth disk after step1  to destination tower Move the n-1 disks that are in helper tower now  to destination tower  using source tower as a helper    Source code in Java      private void towersOfHanoi int n  char source  char destination  char helper          Base case  If there is only one disk move it direct from source to destination     if n  1           System out println  Move from   source   to   destination             else            Step1  Move the top n-1 disks from source to helper         towersOfHanoi n-1  source  helper  destination             Step2  Move the nth disk from source to destination         System out println  Move from   source   to   destination             Step3  Move the n-1 disks those you moved from source to helper in step1              from helper to destination  using source empty after step2  as helper                     towersOfHanoi n-1  helper  destination  source

User · Answer

Actually  the section from where you took that code offers an explanation as well   To move n discs from peg A to peg C   move n-1 discs from A to B  This leaves disc  n alone on peg A move disc  n from A to C move n-1 discs from B to C so they sit on disc  n   It s pretty clear that you first have to remove n - 1 discs to get access to the nth one  And that you have to move them first to another peg than where you want the full tower to appear  The code in your post has three arguments  besides the number of discs  A source peg  a destination peg and a temporary peg on which discs can be stored in between  where every disc with size n - 1 fits   The recursion happens actually twice  there  once before the writeln  once after  The one before the writeln will move n - 1 discs onto the temporary peg  using the destination peg as temporary storage  the arguments in the recursive call are in different order   After that  the remaining disc will be moved to the destination peg and afterwards the second recursion compeltes the moving of the entire tower  by moving the n - 1 tower from the temp peg to the destination peg  above disc n

User · Answer

The first recursive call moves all the pieces except the biggest one from source to by using dest as the auxilary pile  When done all the pieces except the biggest will lie on by and the biggest one is free  Now you can move the biggest one to dest and use another recursive call to move all the pieces from by to dest   The recursive calls won t know anything about the biggest piece  i e  they will ignore it   but that s ok because the recursive calls will only deal with the pieces that are smaller and thus can be moved onto and off the biggest piece freely

User · Answer

This python3 example uses a recursive solution     Hanoi towers puzzle   for each n  you have to move n-1 disks off the n disk onto another peg   then you move the n disk to a free peg   then you move the n-1 disks on the other peg back onto the n disk  def hanoi n       if n    1          return 1     else          return hanoi n-1    1   hanoi n-1    for i in range 1  11       print f n  i   moves  hanoi i       Output   n 1  moves 1 n 2  moves 3 n 3  moves 7 n 4  moves 15 n 5  moves 31 n 6  moves 63 n 7  moves 127 n 8  moves 255 n 9  moves 511 n 10  moves 1023   But of course the most efficient way to work out how many moves is to realise that the answers are always 1 less than 2 n   So the mathematical solution is 2 n - 1

User · Answer

Suppose we want to move a disc from A to C through B then    move a smaller disc to B  move another disc to C  move B to C  move from A to B  move all from C to A    If you repeat all the above steps  the disc will transfer

User · Answer

I am trying to get recursion too   I found a way i think   i think of it like a chain of steps the step isnt constant it may change depending on the previous node   I have to figure out 2 things    previous node step kind after the step what else before call this is the argument for the next call   example  factorial  1 2 6 24 120           or  1 2  1  3  2 1  4  3 2 1 5  4 3 2 1   step multiple by last node  after the step what i need to get to the next node abstract 1  ok  function    n f n-1    its 2 steps process from a-- gt to step--- gt b   i hoped this help just think about 2 thniks not how to get from node to node but node-- step-- node  node-- step is the body of the function step-- node is the arguments of the other function  bye   hope i helped

User · Answer

I feel the pain    Although this is an old post  I think what one really needs to understand  is not the  move this to that  approach but that the answer involves using the side-effect of the recursion   A invaluable help to me was the  The Little Schemer  which teaches one to think and write recursive functions    However  this teaches the reader to use the results of the returned result in the next recursive call    In the Tower of Hanoi  the answer is not in the returned result per se  but in the observation of the returned result    The magic occurs in the succesive rearrangment of the function parameters   Yes the problem is really in three parts    moving a smaller tower to the spare peg moving the last disc to the destination peg moving the remaining tower on the spare peg to the destination peg    In Scheme    define  th n a b c       if  zero  n   done          begin             th  - n 1  a c b              display  list a c               newline              th  - n 1  b a c      th 5  source  spare  destination    However it is the displaying of the function parameters which is the solution to the problem and crucially understanding the double tree like structure of the calls   The solution also conveys the power of proof by induction and a warm glow to all programmers who have wrestled with conventional control structures   Incidently  to solve the problem by hand is quite satisfying    count the number of discs if even  move the first disc to the spare peg  make next legal move  not involving the top disc   Then move the top disc to the destination peg  make the next legal move nittd   Then move the top disc to the source peg  make the next legal move nittd     if odd  move the first disc to the destination peg  make the next legal move  not involving the top disc   Then move the top disc to the spare peg  make the next legal move nittd   Then move the top disc to the source peg  make the next legal move nittd       Best done by always holding the top disc with the same hand and always moving that hand in the same direction   The final number of moves for n discs is 2 n - 1 the move n disc to destination is halfway through the process   Lastly  it is funny how explaining a problem to a colleague  your wife husband or even the dog  even it they not listening  can cement enlightenment

User · Answer

Here is my solution code to Towers of Hanoi problem using recursion with golang   package main  import  fmt   func main         toi 4   src    dest    swap      func toi n int  from  to  swap string        if n    0           return           if n    1           fmt Printf  mov  v  v - gt   v n   n  from  to          return           toi n-1  from  swap  to      fmt Printf  mov  v  v - gt   v n   n  from  to      toi n-1  swap  to  from

User · Answer

After reading all these explanations I thought I d weigh in with the method my professor used to explain the Towers of Hanoi recursive solution  Here is the algorithm again with n representing the number of rings  and A  B  C representing the pegs  The first parameter of the function is the number of rings  second parameter represents the source peg  the third is the destination peg  and fourth is the spare peg   procedure Hanoi n  A  B  C     if n    1     move ring n from peg A to peg B   else     Hanoi n-1  A  C  B       move ring n-1 from A to C     Hanoi n-1  C  B  A   end    I was taught in graduate school to never to be ashamed to think small  So  let s look at this algorithm for n   5  The question to ask yourself first is if I want to move the 5th ring from A to B  where are the other 4 rings  If the 5th ring occupies peg A and we want to move it to peg B  then the other 4 rings can only be on peg C  In the algorithm above the function Hanoi  n-1  A  C  B  is trying to move all those 4 other rings on to peg C  so ring 5 will be able to move from A to B  Following this algorithm we look at n   4  If ring 4 will be moved from A to C  where are rings 3 and smaller  They can only be on peg B  Next  for n   3  if ring 3 will be moved from A to B  where are rings 2 and 1  On peg C of course  If you continue to follow this pattern you can visualize what the recursive algorithm is doing  This approach differs from the novice s approach in that it looks at the last disk first and the first disk last

User · Answer

This is code in C   for Tower of Hanoi  which is recursively called   include  lt iostream gt  void toh int n  char A  char B  char C        if n    1            std  cout  lt  lt   quot Move Disc 1 from  quot   lt  lt  A  lt  lt   quot  to  quot   lt  lt  C  lt  lt  std  endl          return            toh n-1  A  C  B       std  cout  lt  lt   quot Move Disc  quot   lt  lt  n  lt  lt   quot  from  quot   lt  lt  A  lt  lt   quot  to  quot   lt  lt  C  lt  lt std  endl      toh n-1  B  A  C     int main         int numberOfDisc      char A    A   B    B   C    C       std  cout  lt  lt   quot Enter the number of disc   quot       std  cin  gt  gt  numberOfDisc      toh numberOfDisc   A  B  C       return 0

User · Answer

As a CS student  you might have heard about Mathematical induction  The recursive solution of Tower of Hanoi works analogously - only different part is to really get not lost with B and C as were the full tower ends up

User · Answer

Here goes the explanation  Look at the picture -     By calling Movetower 3 a b c   you intend to move all the 3 discs from tower A to tower B  So the sequential calls are -   1  Movetower 3 a b c      No Move needed 2  Movetower 2 a c b      No move needed 3  Movetower 1 a b c      Here is the time to move  move disc1 from a to b 4  Movetower 2 a c b      Returning to this call again  this is the time to move disc2 from a to c 5  Movetower 1 b c a      Again the time to move  this time disc1 from b to c 6  Movetower 3 a b c      Returning to this call again  this is the time to move disc3 from a to b 7  Movetower 2 c b a      Not the time to move 8  Movetower 1 c a b      Here is the time to move  move disc1 from c to a 9  Movetower 2 c b a      Returning to this call again  this is the time to move disc2 from c to b 10 Movetower 1 c a b      Here is the time to move  move disc1 from a to b   Hope it helps     For Animation   https   www cs cmu edu  cburch survey recurse hanoiex html

User · Answer

It s simple  Suppose you want to move from A to C  if there s only one disk  just move it   If there s more than one disk  do   move all disks  n-1 disks   except the bottom one from A to B move the bottom disk from A to C move the n-1 disks from the first step from A to C   Keep in mind that  when moving the n-1 disks  the nth won t be a problem at all  once it is bigger than all the others   Note that moving the n-1 disks recurs on the same problem again  until n-1   1  in which case you ll be on the first if  where you should just move it

User · Answer

public static void hanoi int number  String source  String aux  String dest        if  number    1                System out println source     -  gt    dest             else          hanoi number -1  source  dest  aux           hanoi 1  source  aux  dest           hanoi number -1  aux  source  dest

User · Answer

void TOH int n  int a  int b             Assuming a as source stack numbered as 1  b as spare stack numbered as 2 and  c as target stack numbered as 3  So once we know values of a and b  we can determine c as there sum is a constant number  3 2 1  6            int c   6-a-b  if n  1       cout lt  lt  Move from   lt  lt a lt  lt   to   lt  lt b lt  lt   n     else         Move n-1 disks from 1st to 2nd stack  As we are not allowed to move more than one disks at a time  we do it by recursion  Breaking the problem into a simpler problem      TOH n-1  a  c          Move the last alone disk from 1st to 3rd stack      TOH 1  a  b          Put n-1 disks from 2nd to 3rd stack  As we are not allowed to move more than one disks at a time  we do it by recursion  Breaking the problem into a simpler problem              TOH n-1  c  b       int main      TOH 2  1  3   cout lt  lt  FINISHED                         n   TOH 3  1  3   cout lt  lt  FINISHED                         n   TOH 4  1  3   return 0

User · Answer

Just saw this video today  Recursion  Super Power   in Python  - Computerphile and I think we should definitely have Professor Thorsten Altenkirch s code in here as its a very beautiful and elegant piece of recursion code and its not always that we have a quality video to show in an answer   def move f t         print  move disc from    to      format f t    def hanoi n f h t         if n  0            pass     else           hanoi n-1 f t h          move f t          hanoi n-1 h f t    our hanoi function has 4 parameters    n  number of discs f  origin where discs are  from  h  intermediate step  via   helper  t  final position where we want the discs to be in the end  target     gt  gt  gt  hanoi 4  A   B   C   move disc from A to B  move disc from A to C  move disc from B to C  move disc from A to B  move disc from C to A  move disc from C to B  move disc from A to B  move disc from A to C  move disc from B to C  move disc from B to A  move disc from C to A  move disc from B to C  move disc from A to B  move disc from A to C  move disc from B to C

User · Answer

Tower  N source aux dest      nbsp        if N  1 Then    Write   Source - gt  dest    return end of if  move N-1 disk from peg source to peg aux  call Tower  N-1  source  dest  aux   write source -  dest move N-1 disks from peg aux to peg dest  call Tower  N-1  source  dest  aux   return

User · Answer

Think of it as a stack with the disks diameter being represented by integers  4 3 2 1  The first recursion call will be called 3 times and thus filling the run-time stack as follows   first call        1   Second call      2 1  and third call  3 2 1    After the first recursion ends  the contents of the run-time stack is popped to the middle pole from largest diameter to smallest  first in last out   Next  disk with diameter 4 is moved to the destination   The second recursion call is the same as the first with the exception of moving the elements from the middle pole to destination

User · Answer

In simple sense the idea is to fill another tower among the three defined towers in the same order of discs as present without a larger disc overlapping a small disc at any time during the procedure   Let  A     B  and  C  be three towers   A  will be the tower containing  n  discs initially   B  can be used as intermediate tower and  C  is the target tower    The algo is as follows    Move n-1 discs from tower  A  to  B  using  C  Move a disc from  A  to  C  Move n-1 discs from tower  B  to  C  using  A    The code is as follows in java   public class TowerOfHanoi    public void TOH int n  int A   int B   int C       if  n gt 0           TOH n-1 A C B           System out println  Move a disk from tower   A    to tower     C           TOH n-1 B A C            public static void main String   args        new TowerOfHanoi   TOH 3  1  2  3

User · Answer

def Hanoi n  A  B  C       if n  1   print  move plates to empty peg      else         Hanoi n-1  A  B  C         print  move  str n    to peg   C        Hanoi n-1  B  C  A

User · Answer

I highly recommend this video which illustrates the recursion for this problem in a very understandable way  The key is to understand the repeating pattern in the solution  The problem can be divided into three main sub-problems  Assuming you have n disks that they are placed at rod A  The target rod is C  and you have B as an intermediate  Main problem  move n disks from rod A to rod C by using rod B   Move n-1 disks from rod A to rod B by using rod C  Move the last disk from rod A to rod C  Move n-1 disks from rod B to rod C by using rod A   Sub-problems 1 and 3 are actually solved within the same problem division you see above  Lets take sub problem 1  Sub-problem 1  move n-1 disks from rod A to rod B by using rod C   Move n-2 disks from rod A to rod C by using rod B  Move the last disk from rod A to rod B  Move n-2 disks from rod C to rod B by using rod A   We solve the sub-problem in the same way we solve the main-problem  Our base case will be when the number of disks are equal to 1 then we move it from one rod to target one  that s it  Writing down these steps will help tremendously

User · Answer

package com test recursion           author kamals1986 The Recursive algorithm for Tower of Hanoi Problem The            algorithm grows by power 2 n       public class TowerOfHanoi    private static String SOURCE PEG    B    private static String SPARE PEG    C    private static String TARGET PEG    A    public void listSteps int n  String source  String target  String spare        if  n    1            System out println  Please move from Peg     source     tTo Peg t                    target         else           listSteps n - 1  source  spare  target           listSteps 1  source  target  spare           listSteps n - 1  spare  target  source            public static void main String   args        long startTime   System currentTimeMillis        new TowerOfHanoi   listSteps 18  SOURCE PEG  TARGET PEG  SPARE PEG        long endTime   System currentTimeMillis         System out println  Done in      endTime - startTime    1000                 t seconds

User · Answer

a year ago i had i functional programming course and draw this illustration for the algorithm  hope it helps    0                                                                                                                            1 1                                                                                                                         A - gt  B    1 2                                                                                                                           A - gt  C    1 3                                                                                                                            B - gt  C      2 1                                                                                                                            A - gt  B      3 1                                                                                                                           C - gt  A    3 2                                                                                                                         C - gt  B    3 3                                                                                                                         A - gt  B    The 3 rings problem has been splited to 2 2-rings problem  1 x and 3 x

User · Answer

As some of our friends suggested  I removed previous two answers and I consolidate here   This gives you the clear understanding   What the general algorithm is      Algorithm    solve n s i d    solve n discs from s to d  s-source i-intermediate d-destination       if n  0 return      solve n-1 s d i      solve n-1 discs from s to i Note recursive call  not just move     move from s to d     after moving n-1 discs from s to d  a left disc in s is moved to d     solve n-1 i s d      we have left n-1 disc in  i   so bringing it to from i to d  recursive call      here is the working example Click here

User · Answer

I agree this one isn t immediate when you first look at it  but it s fairly simple when you get down to it   Base case  your tower is of size 1   So you can do it in one move  from source directly to dest   Recursive case  your tower is of size n   1   So you move the top tower of size n-1 to an extra peg  by   move the bottom  tower  of size 1 to the destination peg  and move the top tower from by to dest   So with a simple case  you have a tower of height 2                                                       First step  move the top tower of 2-1   1  to the extra peg  the middle one  lets say                                                        Next  move the bottom disc to the destination                                                         And finally  move the top tower of  2-1  1 to the destination                                                          If you think about it  even if the tower were 3 or more  there will always be an empty extra peg  or a peg with all larger discs  for the recursion to use when swapping towers around

User · Answer

I made a small change to the code here  if you look at the output you can see the small parts pattern are repeating in the parent nodes  Think of it as fractal images   def moveTower height fromPole  toPole  withPole  ar            if height  gt   1          print          3-height    moveTower    height  fromPole  toPole  ar           moveTower height-1 fromPole withPole toPole          moveDisk fromPole toPole height          moveTower height-1 withPole toPole fromPole            print withPole   def moveDisk fp tp height       print         4-height    moving disk        height    from  fp  to  tp    moveTower 3  A   B   C     And the output is    moveTower  3 A B       moveTower  2 A C           moveTower  1 A B               moving disk   from A to B          moving disk    from A to C          moveTower  1 B C                moving disk   from B to C      moving disk     from A to B      moveTower  2 C B            moveTower  1 C A               moving disk   from C to A          moving disk    from C to B          moveTower  1 A B                moving disk   from A to B

User · Answer

The answer for the question  how does the program know  that even is  src  to  aux   and odd is  src  to  dst  for the opening move lies in the program  If you break down fist move with 4 discs  then this looks like this   hanoi 4   src    aux    dst    if  disc  gt  0        hanoi 3   src    dst    aux            if  disc  gt  0                hanoi 2   src    aux    dst                    if  disc  gt  0                        hanoi 1   src    dst    aux                            if  disc  gt  0                                hanoi 0   src    aux    dst                                    END                         document writeln  Move disc    1    from    Src    to    Aux                           hanoi 0   aux    src    dst                                    END                             also the first move with 4 disc even  goes from Src to Aux

[recursion] Tower of Hanoi: Recursive Algorithm

Examples related to recursion

Examples related to towers-of-hanoi