为何汉诺塔递归代码输入为2时与其他数值表现不同？

首先看你给出的简化代码：

def hanoi(disks, source, helper, destination):
    if (disks == 1):
        print('Disk {} moves from tower {} to tower {}.'.format(disks, source, destination))
        return
    hanoi(disks - 1, source, destination, helper)

disks = 3
hanoi(disks, 'A', 'B', 'C')

我们分别拆解两种输入的递归执行流程：

当disks=2时的执行步骤 #

1. 初始调用：hanoi(2, 'A', 'B', 'C')，此时disks≠1，于是调用hanoi(1, 'A', 'C', 'B')——注意这里把原destination（C）传给了新的helper，原helper（B）传给了新的destination。
2. 进入hanoi(1, 'A', 'C', 'B')，disks=1触发print语句，输出Disk 1 moves from tower A to tower B.，之后return，递归结束。

当disks=3时的执行步骤 #

1. 初始调用：hanoi(3, 'A', 'B', 'C')，disks≠1，调用hanoi(2, 'A', 'C', 'B')——同样交换了原destination和helper的位置作为新参数。
2. 进入hanoi(2, 'A', 'C', 'B')，disks≠1，继续调用hanoi(1, 'A', 'B', 'C')——再次交换当前的destination（B）和helper（C）作为新参数。
3. 进入hanoi(1, 'A', 'B', 'C')，disks=1触发print，输出Disk 1 moves from tower A to tower C.，return。
4. 回到上一层hanoi(2, 'A', 'C', 'B')，没有后续代码，直接结束；再回到最外层hanoi(3, 'A', 'B', 'C')，也没有后续代码，递归结束。

核心差异原因 #

两种输入都会触发print语句，只是触发print时的destination参数不同：

• disks=2时，最终触发print的是第二层递归，destination被替换成了原初始调用的helper（B）。
• disks=3时，最终触发print的是第三层递归，destination经过两次参数交换后，变成了原初始调用的destination（C）。

你觉得“仅disks=2时执行输出”是误解，disks=3时同样执行了print，只是因为递归层数多了一层，最终打印的参数和disks=2时不同而已。

内容的提问来源于stack exchange，提问作者Avner Yoffe