Last answered:

13 Nov 2021

Posted on:

12 Nov 2021

0

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.

3 answers ( 0 marked as helpful)
Instructor
Posted on:

12 Nov 2021

0

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

Posted on:

12 Nov 2021

0

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

Posted on:

13 Nov 2021

0

Actually your explanation makes sense.  Please ignore my follow-up question.
Thanks again.

Best
Isaac Kim

Submit an answer