python - 细数汉诺塔的 Action

Question

我在数汉诺塔的步数

In [4]: %paste      
count = 0
def hanoi(n, a, b, c):
    global count 
    if n == 1:
        count += 1
    else:
        hanoi(n - 1, a, c, b)
        hanoi(1, a, b, c)
        hanoi(n - 1, b, a, c)


hanoi(10, "A", "B", "C")
## -- End pasted text --

In [5]: print(count)
1023

上面的解决方案使用了global关键字，
不引入global怎么搞定？

Answer 1

通过一些重构使函数使用一个通用的 count 变量递归:

def hanoi(n, a, b, c):
    count = 0
    if n == 1:
        count += 1
    else:
        count += hanoi(n - 1, a, c, b)
        count += hanoi(1, a, b, c)
        count += hanoi(n - 1, b, a, c)
    return count

输出

>>> hanoi(10, "A", "B", "C")
1023