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:

The number of moves it will take to solve.
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.

uselpa · Accepted Answer · 2013-02-24 14:54:05Z

3

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.

edited Feb 24, 2013 at 14:54

answered Feb 24, 2013 at 14:45

uselpa

19k2 gold badges36 silver badges53 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Rushy Panchal Over a year ago

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

Tachyon Over a year ago

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 :(

uselpa · Accepted Answer · 2013-02-24 17:10:18Z

2

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

answered Feb 24, 2013 at 17:10

uselpa

19k2 gold badges36 silver badges53 bronze badges

Comments

Bálint Aradi · Accepted Answer · 2013-02-24 14:49:00Z

1

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)

answered Feb 24, 2013 at 14:49

Bálint Aradi

3,81220 silver badges22 bronze badges

Comments

Don · Accepted Answer · 2013-02-24 23:53:36Z

1

The simplest way is to use a global var:

count = 0

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

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

edited Feb 24, 2013 at 23:53

answered Feb 24, 2013 at 14:37

Don

17.7k13 gold badges67 silver badges106 bronze badges

1 Comment

Tachyon Over a year ago

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

christopher · Accepted Answer · 2013-02-24 14:39:40Z

0

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).

answered Feb 24, 2013 at 14:39

christopher

27.4k6 gold badges58 silver badges90 bronze badges

Comments

Thomas Thornier · Accepted Answer · 2019-10-18 15:46:55Z

-1

Without time pausing it, it will quickly reach the recursion limit

import time
def loop_forever(count):
    if count == 0:
        print(count)
        time.sleep(1)
        loop_forever(1)
    if count > 0:
        print(count)
        time.sleep(1)
        loop_forever(count + 1)


loop_forever(0)

answered Oct 18, 2019 at 15:46

Thomas Thornier

34 bronze badges

Collectives™ on Stack Overflow

How to create a counter inside a recursive function

6 Answers 6

2 Comments

Comments

Comments

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

2 Comments

Comments

Comments

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related