How to create a counter inside a recursive function

Question

def printMove(source, destination): 
    print('move From ' + str(source) + ' to destination ' + str(destination))
    count +=1
    print count

def Towers(n, source, destination, spare):
    if not count in  locals():
        count = 0
    if n == 1:
        printMove(source, destination)
        count +=1   
    else:
        Towers(n-1, source, spare, destination)
        Towers(1, source, destination, spare)
        Towers(n-1, spare, destination, source)

I wrote this script to solve the "Towers of Hanoi". The script works wonderfully, but I also want to print the number of moves it took to solve the problem. I just cannot figure out how I can put a counter kind of thing which will count:

1. The number of moves it will take to solve.
2. The number of times the "Towers" function was executed.

The if not count in locals(): condition is one of the failed attempts to count the number of moves it will take to solve. Am I on the right track anyway?

Also, is this algorithm efficient? Or is there a better way to solve this?

Moreover, can someone tell me some useful application of Towers of Hanoi and the advantage of recursion? The only one that I could figure out was its simplicity.

Answer 1

One way is to carry the counter through all of the calls like this:

def towers(n, source, destination, spare, count=0):
    if n == 1:
        count += 1
        print('move From', source, ' to destination ', destination, count)
    else:
        count = towers(n-1, source, spare, destination, count)
        count = towers(1, source, destination, spare, count)
        count = towers(n-1, spare, destination, source, count)
    return count

towers(3, 1, 2, 3)

yields

move From 1  to destination  2 1
move From 1  to destination  3 2
move From 2  to destination  3 3
move From 1  to destination  2 4
move From 3  to destination  1 5
move From 3  to destination  2 6
move From 1  to destination  2 7

Regarding efficiency, http://en.wikipedia.org/wiki/Tower_of_Hanoi#Recursive_solution says: "By means of mathematical induction, it is easily proven that the above procedure requires the minimal number of moves possible, and that the produced solution is the only one with this minimal number of moves.".

The main advantage of recursion is that these solutions tend to be elegant. For some kind of problems, the iterative solution is way more complicated to express than the recursive.