汉诺塔递归例题的困惑

LEEFEI571

小甲鱼老师在通过汉诺塔游戏讲解递归的例题代码如下:

def hanoi(n, x, y, z):
    if n == 1:
        print(x, '-->', z)  # 如果只有 1 层，直接将金片从 x 移动到 z
    else:
        hanoi(n-1, x, z, y) # 将 x 上的 n-1 个金片移动到 y
        print(x, '-->', z)  # 将最底下的金片从 x 移动到 z
        hanoi(n-1, y, x, z) # 将 y 上的 n-1 个金片移动到 z
   
n = int(input('请输入汉诺塔的层数：'))
hanoi(n, 'A', 'B', 'C')

当n=3时,小甲鱼老师的分步解析请见所附图片.


我的困惑是每次执行print(x, ‘--->’, z)时,为和x,z取的值是上一层数值?比如,递归到n=2时,这里print(x, ‘--->’, z)中的x,z分别取的值是n=3时,x,y,z分别是’A’,’B’,’C’时的值,所以print(x, ‘--->’, z)打印结果是A ---> C,而非取的是上面n=2, x,y,z分别是’A’,’C’,’B’时的值.
同样的情况也出现在递归到n=1时, print(x, ‘--->’, z)中的x,z分别取的值均来自n=2时对应的x,z的值,而非取自本层级n=1时x,z的值.
麻烦各位大佬指点一下,谢谢!

FishC

在递归函数中，每一次函数调用都会有自己独立的一组参数，不会影响其他调用的参数。这意味着每一层递归调用都可以保存和使用自己的参数值。

我们来看你的这个例子：

当你调用 `hanoi(n=3, x='A', y='B', z='C')` 时，整个过程如下：

1. **第一次调用：`hanoi(3, 'A', 'B', 'C')`**
   - 这将调用 `hanoi(2, 'A', 'C', 'B')`

2. **第二次调用：`hanoi(2, 'A', 'C', 'B')`**
   - 这将调用 `hanoi(1, 'A', 'B', 'C')`
   
3. **第三次调用：`hanoi(1, 'A', 'B', 'C')`**
   - 直接打印 `A --> C`

返回到第二次调用后，继续执行 `print(x, '-->', z)`，这里的 `x` 和 `z` 是第二次调用的参数 `'A'` 和 `'B'`，所以打印 `A --> B`。

然后，第二次调用会执行 `hanoi(1, 'C', 'A', 'B')`，这又是一个独立的调用，它会打印 `C --> B`。

依此类推，你可以看到每一个 `print` 调用时参数都是专属于该递归调用的参数。每一层这个 `x`, `y`, `z` 的值是根据它们具体在那一层是如何传入函数的，而不是从其他地方继承的。因此：

- `print` 使用的是当前递归调用中经过参数传递的 `x` 和 `z”。

希望这样能帮助你理解每次递归调用中参数的变化！如果还有疑惑，请随时问。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

15631918586

君不见，黄河之水天上来，奔流到海不复回。

不二如是

从鱼油截图来看，踩了一个容易混淆的地方是：

每次进入 hanoi 函数时，形参 x, y, z 都是「当前调用」独立的一组局部变量，它们的取值来自调用它的那一层所传进来的实参，而不是直接“继承”外层函数的变量。

也就是说，当你写：

hanoi(n-1, x, z, y)
print(x, '-->', z)
hanoi(n-1, y, x, z)

外层（例如 n=3 时）的 x, y, z 可能是 'A', 'B', 'C'；

一旦调用 hanoi(n-1, x, z, y)（即 hanoi(2, 'A', 'C', 'B')），这一层（n=2）的 x, y, z 就分别是 'A', 'C', 'B'，与外层无关。

而当执行到：

print(x, '-->', z)

要看到底是在哪一层（哪个调用）里执行的 print。

在 n=3 的调用栈里执行到 print 时，当然用的就是「n=3那一层」的 x='A' 和 z='C'；

若是在「n=2那一层」的函数体里执行到 print，用的就是「n=2那一层」的 x='A' 和 z='B'。

之所以看起来像是“用了上一级的值”，是因为我们在递归时恰好把外层的形参按某种顺序又传给了下一层，所以字面上你会看到“参数名相同，实参却是上一层的部分变量”。

但本质上每个调用都拥有自己独立的一套 x, y, z，互不冲突。

只要记住函数的形参在每次调用中都是局部变量即可。

print(x, '-->', z)始终输出的是当前这一次调用里传进来的 x 和 z。