Tower of Hanoi Recursion - need help understanding call stack

Python
1

Hello everyone. I have completed the tutorial, but I want to understand it deeper, and my brain breaks on trying to understand two things:

  1. How to track which recursive function call is invoked during the unwinding?

  2. How exactly the program differentiaties even and odd number of disks? When number is odd, first disk gets placed on Target rod; when it’s even, first disk goes on Auxiliary rod. How does the program know that?

2

To save me trying to wrap my head around this again right now, I can share with you the notes which I made at the time at which I completed this project.
I hope it might help to clarify!

This project works on the premise that the number of rods is always three, but that the number of disks can vary.
The allowed disk movements between the rods exhibit a repetitive pattern occurring every three moves (regardless of the number of disks).
For example, movements between rod A and rod C are allowed on the first, the fourth and the seventh move, where the remainder of the division between the move number and 3 (number of disks) is equal to 1.

To solve with 3 disks and 3 rods for instance:

  1. A=>C (remainder 1)
  2. A=>B (remainder 2)
  3. C=>B (remainder 0)
  4. A=>C
  5. B=>A
  6. B=>C
  7. A=>C

NOTE: Moves 5 and 6 are equivalent to moves, 2 and 3, but backwards.

The helper function make_allowed_move() simply determines whether the move between a given pair of rods is forwards or backwards, and then declares the move and amends the lists accordingly.

The main function move() decides between which two rods each move is to be made, before invoking make_allowed_move().
As the remainder will follow the repeating pattern 1, 2, 0 (regardless of number of disks), move() determines the pattern of moves on the basis of the remainder and whether the number of disks is odd or even.

Moves 1, 4, 7, 10, 13 etc when remainder == 1:
if odd number of disks, move A=>C (or reverse)
if even number of disks, move A=>B (or reverse)

Moves 2, 5, 8, 11, 14 etc when remainder == 2:
if odd number of disks, move A=>B (or reverse)
if even number of disks, move A=>C (or reverse)

Moves 3, 6, 9, 12, 15 etc when remainder == 0:
move B=>C (or reverse)

In terms of the recursive solution:

As the function (as a whole) moves n disks from source to target, it’s easy to break this problem down into smaller recursive steps:

  1. Move n-1 disks from source to auxiliary.
  2. Move largest disk from source to target
  3. Move n-1 disks from auxiliary to target.

The recursive nature of this solution means that when move(n-1, 'A', 'C', 'B') is called (to move n-1 disks from source to auxiliary), this function call in turn breaks down the task of moving n-1 disks into moving n-2 disks from source to target, 1 disk from source to auxiliary and then n-2 disks from target to auxiliary… and so the process continues until we reach the base case (when there are no more disks to move), when the function returns and the process unwinds from the inside out.

A couple of links which also helped me out at the time:
Tower of Hanoi Algorithm: Recursive Solution & Python Coding

…and:

3

I found a good explanation that helped me with recursion in general which visualized recursive calls being added to a stack:

https://www.youtube.com/watch?v=ivl5-snqul8