Hey kids,

This lets you play test recursion at home without the Fisher Price Toys. He he! http://www.cs.cmu.edu/~cburch/survey/recurse/hanoi.html Have fun.

Question

Hey kids,

   This lets you play test recursion at home without the Fisher Price Toys. He he! http://www.cs.cmu.edu/~cburch/survey/recurse/hanoi.html Have fun.

rsmith6559 · Answer

IMHO, reversing a string, testing for a palindrome and converting base 10 numbers to other bases are more understandable programs to learn recursion than the Towers of Hanoi or the Towers of Brahma.

anonymous · Answer

cool link, always looking for free resources

anonymous · Answer

I agree that it's not the best example for recursion but is fun to play with. 
Something to try is this.
def printMove(fr, to):
    global numCalls
    numCalls += 1
##    print('move from ' + str(fr) + ' to ' + str(to))

def Towers(n, fr, to, spare):
    if n == 1:        
        printMove(fr, to)        
    else:        
        Towers(n-1, fr, spare, to)        
        Towers(1, fr, to, spare)        
        Towers(n-1, spare, to, fr)

numCalls = 0
Towers(26, 'A', 'B', 'C')
print numCalls

notice I commented out the print in the printMove() function.

This takes a little time to run but it gives you an idea of the complexity.
Imagine how long it would take for 64 disks. Would I dare let it run that long?
I don't know. Maybe some day. I would first want to put in some time start and time end markers.

anonymous · Answer

For complexity I get 2^n-1. Is that about right?

anonymous · Answer

For 64 disks then it would be 18446744073709551615 moves.