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.

Solution 1

The answer above should give you your answer :)

In terms of efficiency, it looks like your solution will work for n towers. If you wish to solve the classic problem more efficiently, look at this link:

http://www.vogella.com/articles/JavaAlgorithmsTowersOfHanoi/article.html

Finally, recursion is designed to make very simplistic algorithms that can perform complex calculations with basic code. The disadvantage is that it is memory intensive (each call places a new memory address on the stack of the last call).

Solution 2

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.

Solution 3

The simplest way is to use a global var:

count = 0

def runTowers(...):
    global count
    count = 0
    Towers(...)

def Towers(...):
    global count
    count += 1
    ...

Solution 4

I like this version even better, without the extra parameter 'count':

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

print(towers(3, 1, 2, 3))

yields

move From 1  to destination  2
move From 1  to destination  3
move From 2  to destination  3
move From 1  to destination  2
move From 3  to destination  1
move From 3  to destination  2
move From 1  to destination  2
7

Solution 5

You could make a function object instead of a function:

class Towers:

    def __init__(self):
        self.count = 0

    def __call__(self, n, source, destination, spare):
        if n == 1:
            self.printMove(source, destination)
            self.count +=1   
        else:
            self(n-1, source, spare, destination)
            self(1, source, destination, spare)
            self(n-1, spare, destination, source)

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

towers = Towers()
towers(3, 1, 2, 2)

View more solutions

Comments

[Rushy Panchal]

Ah, I was just about to post this. Oh well, you got to it first :)

[Tachyon]

Oh.. Thanks .. .. This works well in Python. I am actually working to port this code on an 8051 based system now but "count =0" won't work in C :(

[Tachyon]

Yea. but then it will start the count from the previous value when I run it again. :)