2

I am not fully understanding the Towers of Hanoi. The recursion is very elegant and the answer has eluded me for a very long time. I am currently learning python, so lets use python.

def TowerOfHanoi(n,from_rod, to_rod, aux_rod):
    if n==1:
        print ("Move disk 1 from rod", from_rod, "to rod", to_rod)
        return
    TowerOfHanoi(n-1,from_rod, aux_rod, to_rod)
    print ("Move disk", n, "from rod", from_rod, "to rod", to_rod)
    TowerOfHanoi(n-1,aux_rod, to_rod, from_rod)

n=4
TowerOfHanoi(n,'A', 'C', 'B')]

This is the correct code for the Tower of Hanoi. I understand the two calls within the function. I have drawn a picture that shows the disk moving from from_rod to aux_rod, then the next call moves it from aux_rod to to_rod. That makes sense now.

I do not understand how the function is calling the disks in that order and how the program continues for so long. If you understand the TowersOfHanoi in C, Java, pseudocode, python, or Matlab then your help is greatly appreciated.

Jordan Greenhut
  • 143
  • 3
    You likely want this on Stack Overflow or a programming stack exchange, for example: https://stackoverflow.com/questions/tagged/python – Moo Aug 29 '19 at 20:32
  • That maybe so. However, I am looking for a mathematics explanation anyways. The pseudocode would suffice. – Jordan Greenhut Aug 29 '19 at 20:33
  • Move disk 1 from rod A to rod B Move disk 2 from rod A to rod C Move disk 1 from rod B to rod C Move disk 3 from rod A to rod B Move disk 1 from rod C to rod A Move disk 2 from rod C to rod B Move disk 1 from rod A to rod B Move disk 4 from rod A to rod C Move disk 1 from rod B to rod C Move disk 2 from rod B to rod A Move disk 1 from rod C to rod A Move disk 3 from rod B to rod C Move disk 1 from rod A to rod B Move disk 2 from rod A to rod C Move disk 1 from rod B to rod C – Jordan Greenhut Aug 29 '19 at 20:38
  • How does it change the disks? – Jordan Greenhut Aug 29 '19 at 20:38
  • Is n changing? How and where is it changing? – Jordan Greenhut Aug 29 '19 at 20:38
  • You do the recursive call with the value $n-1$ for the formal parameter $n$. This is really a programming question, not a math question. – saulspatz Aug 29 '19 at 20:46
  • That's fair. Why doesn't the recursive call just happen twice and only for 3 because n=4 and n-1 = 3?? – Jordan Greenhut Aug 29 '19 at 20:47

1 Answers1

1

This is the C++ (a very similar language to C) code of Hanoi's Tower:

enter image description here

And here the output for $n=4$:

enter image description here

Matteo
  • 6,581