汉诺塔算法使用递归，同时显示步数

Question

我们都知道 python 解决汉诺塔问题的代码如下：

def hanoi(n, a, b, c):
    if n == 1:
        print a, '-->', c
        return
    hanoi(n-1, a, c, b)
    print a, '-->', c
    hanoi(n-1, b, a, c)

hanoi(4, 'A', 'B', 'C')

我的问题是在哪里添加 print('stepCount ={}'.format(stepCount)) 以显示每一步的 stepCount。

*****更新和澄清***** 而上面代码的输出显示：

A > C
A > B
C > B
A > C
B > A
B > C
A > C

我想知道是否可以将 print 语句添加到代码中以将输出更改为：

stepCount: 1
A > C
stepCount: 2
A > B
stepCount: 3
C > B
stepCount: 4
A > C
stepCount: 5
B > A
stepCount: 6
B > C
stepCount: 7
A > C

Answer 1

当然，您可以更新它以打印出步数。您可以通过递归传递一个额外的参数来跟踪递归调用开始时的步骤号，然后在调用结束后让递归 return 成为最后的步骤号。需要考虑的一些事情：

您会使用什么初始值？
您将如何从各个递归调用中捕获 return 值？
您会如何处理捕获的值？

Answer 2

@emplatetypedef 描述了如下解决方案：

def hanoi(n, a, b, c, count):
    if n > 0:
        count = hanoi(n-1, a, c, b, count)
        count += 1
        print('stepCount: {}'.format(count))
        print('{} --> {}'.format(a, c))
        count = hanoi(n-1, b, a, c, count)
    return count

hanoi(3, 'A', 'B', 'C', 0)

也可以用全局变量来实现（是的，我知道呃...）：

def hanoi(n, a, b, c):
    global stepCount
    if n > 0:
        hanoi(n-1, a, c, b)
        stepCount += 1
        print('stepCount: {}'.format(stepCount))
        print('{} --> {}'.format(a, c))
        hanoi(n-1, b, a, c)


stepCount = 0
hanoi(3, 'A', 'B', 'C')

OUTPUT（两个代码片段）

stepCount: 1
A --> C
stepCount: 2
A --> B
stepCount: 3
C --> B
stepCount: 4
A --> C
stepCount: 5
B --> A
stepCount: 6
B --> C
stepCount: 7
A --> C

汉诺塔算法使用递归，同时显示步数

Hanoi Tower Algorithm using recursion, while show the step count

algorithm

towers-of-hanoi