Recursive method used in Tower of Hanoi problem
From the code presented for Tower of Hanoi problem:
# We have 3 towers A, B and C or 3 Stacks
A = [14,13,12,11,10,9,8,7,6,5,4,3,2,1]
B = []
C = []
# According to our rules, if we want to move all disks 3,2 and 1 from A to C, we first move two disks from A to B.
# We then move the base disk from A to C and then the stack of two from B to C
count = 0
def towers_of_hanoi(A,B,C,n):
global count
if n == 1:
disk = A.pop()
C.append(disk)
count +=1
else:
towers_of_hanoi(A,C,B,n-1)
towers_of_hanoi(A,B,C,1)
towers_of_hanoi(B,A,C,n-1)
return count
Question 1:
If you set n=3 while keeping 14 disks in peg A this routine works and produces following results:
towers_of_hanoi(A,B,C,3) = 7
A = [14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4]
B = []
C = [3, 2, 1]
There is no constraint on 'n' in the code. How does Python know to stop after moving 3 disks from A to C?
Question 2:
Again, since there is no constraints on 'n' why doesn't it work for n<0?
If you set n<0 Python throws an error.
Hey 이삭,
Thank you for your question!
The constraint on n
is given by the base case, namely n == 1
. Therefore, it knows to not go below n = 1
.
Hope this helps!
Kind regards,
365 Hristina
Hi Hristina, thanks for responding to my question.
I'm confused by the presence of the 'else' statement. It appears any value for n other than n==1, including n<0 would fall under the 'else' statement in which towers_of_hanoi(A,B,C,1) would always be executed. In fact, this would be an infinite loop until the stack A gets exhausted and becomes empty. What am I missing? - I would appreciate if you could walk me through step by step understanding this code. Thanks once again for your help.
Best
Isaac Kim
Actually your explanation makes sense. Please ignore my follow-up question.
Thanks again.
Best
Isaac Kim