如何在递归函数中创建计数器

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)

我写了一个脚本来解决“汉诺塔”问题。这个脚本运行得很好，但我还想打印出解决这个问题所需的移动次数。我就是想不出怎么加一个计数器来计算：

1. 解决问题所需的移动次数。
2. “汉诺塔”这个函数被执行的次数。

if not count in locals():这个条件是我尝试计算解决所需移动次数时失败的一个例子。不知道我是不是在正确的方向上？

另外，这个算法效率高吗？还是说有更好的解决办法？

还有，能不能告诉我汉诺塔的一些有用应用和递归的优点？我能想到的只有它的简单性。

Answer 1

我更喜欢这个版本，因为它没有多余的参数'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))

结果是

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

Answer 2

一种方法是通过所有的调用来传递计数器，像这样：

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)

这样可以得到

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

关于效率，http://en.wikipedia.org/wiki/Tower_of_Hanoi#Recursive_solution上说：“通过数学归纳法，可以很容易证明上述过程需要的移动次数是最少的，并且产生的解决方案是唯一的最少移动次数的方案。”

递归的主要优点是，这些解决方案往往很优雅。对于某些类型的问题，迭代的解决方案比递归的要复杂得多。

Answer 3

上面的回答应该能帮你解决问题 :)

从效率的角度来看，你的方案应该能处理 n 个塔。如果你想更高效地解决这个经典问题，可以看看这个链接：

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

最后，递归是一种设计用来让简单的算法能够用基本的代码完成复杂计算的方法。缺点是它比较耗内存（每次调用都会在上一个调用的内存堆栈上放一个新的内存地址）。