Towers of Hanoi First Move I've finally more or less understood the recursive algorithm for solving the Towers of Hanoi. My Python code is below.

However one thing still bugs me - I can't yet work out how this simple seeming algorithm can "know" which move to make first - whether to the destination peg or the spare peg.

I can see it depends on whether there is an odd or even number of discs, and I understand how the algorithm works, thanks to this great article: https://www.geeksforgeeks.org/c-program-for-tower-of-hanoi/

It's just that first move that remains a mystery to me. Any clarification musch appreciated.

def hanoi(n, from_peg, to_peg, spare_peg):
    if n == 1:
        print("Moving disc from " + from_peg + " to " + to_peg)
        return
    hanoi(n-1, from_peg, spare_peg, to_peg)
    print("Moving disc from " + from_peg + " to " + to_peg)
    hanoi(n-1, spare_peg, to_peg, from_peg), 

print (hanoi(4, 'A', 'C', 'B'))
If you trace the recursion calls that your algorithm makes before it prints its first line, you will have if the first call is  hanoi(n, 'A', 'B', 'C') : 

hanoi(n, 'A', 'B', 'C')
hanoi(n-1, 'A', 'C', 'B')
hanoi(n-2, 'A', 'B', 'C')
...
hanoi(1, 'A', $ , €)
Moving disc from A to $


To see if $ is equal to B or C, you just have to remark that the value of to_peg and spare_peg alternate each time so the disk to move only depends on the parity of n. In our example :

If n is odd then \$ = B and otherwise, \$ = C