python - 有人可以一步一步地解释这个功能在做什么吗

Question

def hanoi(n,f,v,t):
    if n == 0:
        pass
    else:
        hanoi(n-1,f,t,v)
        print(f"Move disc from {f} to {t}.")
        hanoi(n-1,v,f,t)

hanoi(3,"a","b","c")

我正在研究递归，但我无法理解这个“汉诺塔”函数。它工作正常，但我不明白它到底在做什么。例如，函数打印的指令之一是:
“将圆盘从 c 移动到 b。”
但在我看来 {f} 只能是“a”或“b”？
当 (n = 2) 时似乎很容易理解，因为它调用 (n = 1) 打印“将光盘从 a 移动到 b”。
然后返回到 (n = 2)，打印“将光盘从 a 移动到 c”。
然后它调用 (n = 1) 打印“将光盘从 b 移动到 c。”
但我不明白 n 的值越大会发生什么。

Answer 1

首先用伪代码来表述问题是有帮助的:

move_tower(height_of_tower, "origin", "destination", "helper"):
    if height_of_tower is 1:
        move disk directly from "origin" to "destination"
    else:
        move height_of_tower-1 disks from "origin" to "helper" using "destination"
        move remaining single disk from "origin" to "destination"
        move height_of_tower-1 disks from "helper" to "destination" using "origin"

此伪代码可以立即转换为 Python 代码。 n = 0 的基本情况只是另一种写法，因为对于 n=1 else block 中的两个函数调用都不会做任何事情(基本情况n=0 只是通过)。

递归函数有两个重要的属性:1. 首先，它定义了一个带有平凡解的基本情况，直接给出。2. 否则，它解释了如何从部分解决方案中获得解决方案；为此，可以使用任何函数，包括递归函数本身。唯一重要的是它是用减少的输入数据调用的，因此在某个时候会命中基数。

关于您的问题:“但在我看来 {f} 只能是“a”或“b”？......但我不明白 n 的值越大会发生什么。“

不，{f} 视情况而定成为“起点”、“目的地”和“辅助”杆。它可以帮助写下小 n 的函数调用，例如n = 3，并绘制递归树(一个流行的例子是 recursive Fibonacci function )。例如，如果 n = 3，则会发生以下情况:

1. 调用 move_tower(2, "origin", "helper", "destination") = 将 2 个磁盘从“origin”转移到“helper”(您已经知道这是如何工作的，对吧？)
2. 将剩余的磁盘直接从“起点”移动到“终点”
3. move_tower(2, "helper", "destination", "origin") = 使用 "origin"作为助手将 2 个磁盘从 "helper"(我们在步骤 1 中放置它们的地方)转移到 "destination"

一般来说，很难真正“递归思考”。将您的函数视为常规函数会有所帮助，它可以使用任何其他函数来实现所需的结果，包括它自身，但数据集会减少。基本情况确保它不会永远运行。