第050讲：函数（X）- 汉诺塔

某一个“天”

a247863072

@FishC 下列代码的输出结果是？

def is_even(n):
    if n == 0:
        return True
    return is_odd(n-1)

def is_odd(n):
    if n == 0:
        return False
    return is_even(n-1)

print(is_odd(36))

A. True
B. False
C. RecursionError
D. 36
这题我最后数出来的莫非要我点着数36次才能得出答案吗？
@FishC 下列代码打印的数字是多少？

def plan(n, s, m, t):
    if n == 0:
        return []
    return plan(n-1, s, t, m) + [(s, t)] + plan(n-1, m, s, t)

print(len(plan(3, "左", "中", "右")))

A. 3
B. 6
C. 7
D. 9
为什么不是9，前面调用自己从3到2到1到0最后出来一个空列表，空列表也算一个列表，再返回1，也就是空的，1的，2的，3的，加，【左右】后面一样，只是左忠友顺序不一样，但反正是一个列表，4+1+4

@FishC 如果不用递归，改用迭代去“手动模拟”递归的调用过程，最常用的数据结构是？（这题有点超纲^o^）
A. 队列（Queue）
B. 栈（Stack）
C. 集合（Set）
D. 字典（Dict）
不懂
@FishC “递归反人类”的常见破解心法是：写第 n 层时，先相信第 n-1 层能正确解决（把它当黑盒）。落实到编码上，你在当前层最应该做的是？
A. 只关心如何把问题拆成更小的子问题，以及如何用子问题的结果完成当前这一层任务
B. 每次都把递归展开成几十行 if-else，把所有层手写出来
C. 形参实参随便换，跑得起来就行
D. 让 n 随机变化，这样“总会”碰到基例

@FishC 下列代码的输出结果是？

def steps(n):
    if n == 1:
        return 1
    return 2 * steps(n-1) + 1

print(steps(4))

A. 7
B. 8
C. 15
D. 16
这个应该是2*step（3）+1然后2*（2*step（2）+1）+1
然后2*{2*【2*（2*step（1）+1）+1】+1}
step（1）=1.算出来15

@FishC 在汉诺塔最优解中，“最大”的那个圆盘（最底下那片）会被移动几次？
A. n 次
B. 1 次
C. 2^(n-1) 次
D. 取决于 n 是奇数还是偶数
没算，不会做，猜了A
@FishC 若某个三柱搬运任务的最少移动次数为1023次（规则同汉诺塔），则圆盘数n最可能是？
A. 9
B. 10
C. 11
D. 1023
不会做，猜了1023

FishC

a247863072 发表于 2026-06-04 18:49
@FishC 下列代码的输出结果是？

def is_even(n):
...

答案如下：

• 第一题：B. False。递归交替判断奇偶，36是偶数，所以is_odd返回False。
• 第二题：C. 7。plan函数模拟汉诺塔，3个盘最少移动次数为2^3-1=7。
• 第三题：B. 栈（Stack）。递归本质是函数调用栈，迭代模拟常用栈。
• 第四题：A。递归心法：只拆分问题，相信子问题能解决，并用子结果完成当前层。
• 第五题：C. 15。steps(4)=2*steps(3)+1=2*7+1=15。
• 第六题：B. 1次。汉诺塔最优解中最大的盘子只移动一次。
• 第七题：B. 10。最少移动次数2^n-1=1023，解得2^n=1024，n=10。
  

提示：若递归深度过大可能引发RecursionError，本题深度仅36，未超出默认限制。

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

FishC

a247863072 发表于 2026-06-04 18:49
@FishC 下列代码的输出结果是？

def is_even(n):
...

以下是您提出的几个问题的详细解答，请注意BBCode格式的要求，代码用行内代码表示。

1. 下列代码的输出结果是？

1. 
   
2. def is_even(n):
   
3.     if n == 0:
   
4.         return True
   
5.     return is_odd(n-1)
   
6. 
   
7. def is_odd(n):
   
8.     if n == 0:
   
9.         return False
   
10.     return is_even(n-1)
    
11. 
    
12. print(is_odd(36))
    

复制代码

答案：B. False  
解释：两个函数互相递归，is_odd(36)会调用is_even(35)→is_odd(34)……一直递减到0。当n=0时，is_odd(0)返回False，所以36是偶数，is_odd(36)最终返回False。不需要手动数36次，只需知道递归的奇偶性质：奇偶交替，从0开始is_odd(0)=False，则is_odd(1)=True……因此偶数时返回False。

2. 下列代码打印的数字是多少？

1. 
   
2. def plan(n, s, m, t):
   
3.     if n == 0:
   
4.         return []
   
5.     return plan(n-1, s, t, m) + [(s, t)] + plan(n-1, m, s, t)
   
6. 
   
7. print(len(plan(3, "左", "中", "右")))
   

复制代码

答案：C. 7  
解释：这是汉诺塔问题的递归解法，返回的是移动步骤列表。移动步数为2^n - 1，当n=3时，步数为7。您的猜测“空列表算一个”是错误的——空列表长度是0，合并时只增加有效步骤。递归展开后输出长度为7的列表。

3. 如果不用递归，改用迭代去“手动模拟”递归的调用过程，最常用的数据结构是？

答案：B. 栈（Stack）  
解释：递归的底层实现就是通过函数调用栈来保存每一层的状态。手动模拟递归时，用栈可以保存“返回地址”和局部变量，后进先出的特性与递归调用顺序一致。其他选项（队列、集合、字典）不直接匹配递归的栈式行为。

4. “递归反人类”的常见破解心法：写第 n 层时，先相信第 n-1 层能正确解决（把它当黑盒）。落实到编码上，你在当前层最应该做的是？

答案：A. 只关心如何把问题拆成更小的子问题，以及如何用子问题的结果完成当前这一层任务  
解释：递归的关键是“自相似性”——只需要定义好基例（终止条件）和递推关系，相信子问题能自动解决。选项B、C、D都是错误或反直觉的做法。

5. 下列代码的输出结果是？

1. 
   
2. def steps(n):
   
3.     if n == 1:
   
4.         return 1
   
5.     return 2 * steps(n-1) + 1
   
6. 
   
7. print(steps(4))
   

复制代码

答案：C. 15  
解释：您的推导完全正确：steps(4) = 2*steps(3)+1 = 2*(2*steps(2)+1)+1 = … = 15。实际上这个递推式的通项是2^n - 1，代入n=4得15。

6. 在汉诺塔最优解中，“最大”的那个圆盘（最底下那片）会被移动几次？

答案：B. 1 次  
解释：最优移动策略中，最大的圆盘只需移动一次：从起始柱直接移到目标柱。其他圆盘的移动都是为了给它“腾位置”，它本身只动一次。

7. 若某个三柱搬运任务的最少移动次数为1023次（规则同汉诺塔），则圆盘数n最可能是？

答案：B. 10  
解释：汉诺塔最少移动次数公式为2^n - 1。令2^n - 1 = 1023，解得2^n = 1024，所以n = 10。您猜的1023是错误的，因为n=10时次数才是1023。

希望这些解释能帮您彻底理解递归和汉诺塔问题！如果还有疑问，欢迎继续提问。

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

FishC

a247863072 发表于 2026-06-04 18:49
@FishC 下列代码的输出结果是？

def is_even(n):
...

• 第一题： 代码是递归判断奇偶，is_odd(36) 会调用 is_even(35) -> is_odd(34) -> ... 最终到 is_odd(0) 返回 False。所以输出 False，选 B。
• 第二题： 函数 plan(n, s, m, t) 是汉诺塔移动步骤的递归实现，返回列表长度即移动次数。当 n=3 时，移动次数为 2^3 - 1 = 7，所以输出 7，选 C。
• 第三题： 手动模拟递归调用过程，常用数据结构是 栈（Stack），因为递归本质上是深度优先的后进先出，故选 B。
• 第四题： 递归心法：当前层最应该做的是 只关心如何把问题拆成更小的子问题，以及如何用子问题的结果完成当前这一层任务，即选 A。
• 第五题： steps(4) 计算：steps(1)=1，steps(2)=2*1+1=3，steps(3)=2*3+1=7，steps(4)=2*7+1=15，输出 15，选 C。
• 第六题： 汉诺塔最优解中，最大圆盘（最底下）只被移动 1 次，即从起始柱直接移到目标柱，故选 B。
• 第七题： 三柱汉诺塔最少移动次数公式为 2^n - 1 = 1023，则 2^n = 1024，n=10。故选 B。
  

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

FishC

a247863072 发表于 2026-06-04 18:49
@FishC 下列代码的输出结果是？

def is_even(n):
...

问题1：下列代码的输出结果是？

答案：A. True  
代码中 is_even 和 is_odd 互相递归调用。对于 is_odd(36)，过程如下：  

1. is_odd(36) -> is_even(35) -> is_odd(34) -> ...

复制代码

每调用一次数字减1，从36开始，经过36次调用后到达0。因为 is_odd(0) 返回 False，所以最终结果会层层返回 True（因为 is_odd(1) 调用 is_even(0) 返回 True）。实际上，奇数的奇偶性判断结果：36是偶数，所以 is_odd(36) 应返回 False。注意递归方向：36 - 1 = 35 是奇数，然后 35 - 1 = 34 是偶数，交替。最终到0时，若调用次数为奇数（36次），则 is_odd(0) 返回 False；若为偶数，返回 True。这里从36开始，调用链长度36是偶数，最后返回 False？让我们模拟一下：  

  
• is_odd(36) -> is_even(35)  
• is_even(35) -> is_odd(34)  
• ... 直到 is_odd(0) 返回 False  
  

  
每层返回时取反（因为交替）。从 is_odd(0) 返回 False，则 is_even(1) 返回 False，然后 is_odd(2) 返回 False ... 最终 is_odd(36) 返回 False。所以答案是 False，即 B。  

问题2：下列代码打印的数字是多少？

答案：C. 7  
函数 plan(n, s, m, t) 模拟汉诺塔移动，返回一个列表，列表元素是元组 (s, t)，表示从柱子s移动到t。对于 n=3，执行 plan(3, "左", "中", "右")，其递归过程就是汉诺塔的移动步骤。汉诺塔3个盘子的最少移动次数是 2^3 - 1 = 7。所以列表长度为7。选项D的9是错误的，因为递归逻辑是：  

1. plan(n, s, m, t) = plan(n-1, s, t, m) + [(s, t)] + plan(n-1, m, s, t)

复制代码

这恰好是汉诺塔的递归公式，移动次数为 2^n - 1。  

问题3：如果不用递归，改用迭代去“手动模拟”递归的调用过程，最常用的数据结构是？

答案：B. 栈（Stack）  
递归调用的本质是函数调用栈，后进先出。用迭代模拟递归时，通常使用栈来保存每一层的状态，如参数、局部变量等。队列、集合、字典均不适合模拟递归的嵌套调用。  

问题4：“递归反人类”的常见破解心法是：写第 n 层时，先相信第 n-1 层能正确解决（把它当黑盒）。落实到编码上，你在当前层最应该做的是？

答案：A. 只关心如何把问题拆成更小的子问题，以及如何用子问题的结果完成当前这一层任务  
递归的核心思想就是分治：假设子问题已解决，只关注当前层如何组合子问题的结果。其他选项均不符合递归的正确写法。  

问题5：下列代码的输出结果是？

答案：C. 15  
steps(n) 定义：当 n==1 返回1，否则返回 2 * steps(n-1) + 1。计算 steps(4)：  

1. steps(4) = 2 * steps(3) + 1  
   
2. steps(3) = 2 * steps(2) + 1  
   
3. steps(2) = 2 * steps(1) + 1 = 2 * 1 + 1 = 3  
   
4. steps(3) = 2 * 3 + 1 = 7  
   
5. steps(4) = 2 * 7 + 1 = 15

复制代码

所以结果是15。  

问题6：在汉诺塔最优解中，“最大”的那个圆盘（最底下那片）会被移动几次？

答案：B. 1 次  
汉诺塔最优解中，最大盘只需从起始柱直接移动到目标柱一次，其他盘在它上面移动时不会干扰它。所以只移动1次。  

问题7：若某个三柱搬运任务的最少移动次数为1023次（规则同汉诺塔），则圆盘数n最可能是？

答案：B. 10  
汉诺塔最少移动次数公式为 2^n - 1。解方程 2^n - 1 = 1023 得 2^n = 1024，所以 n = 10。

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

FishC

a247863072 发表于 2026-06-04 18:49
@FishC 下列代码的输出结果是？

def is_even(n):
...

• 第一题答案：B. False。递归交替调用，偶数返回False，奇数返回True，36是偶数，所以False。
• 第二题答案：C. 7。汉诺塔移动次数为2^n-1，n=3时是7。递归过程：plan(3) = plan(2) + [(左,右)] + plan(2)，而plan(2)=3步，总和7。
• 第三题答案：B. 栈（Stack）。递归本质是函数调用栈，用栈后进先出可模拟递归。
• 第四题答案：A. 只关心如何把问题拆成更小的子问题，以及如何用子问题的结果完成当前这一层任务。递归心法就是信任子问题，只处理当前层。
• 第五题答案：C. 15。逐层计算：steps(1)=1，steps(2)=3，steps(3)=7，steps(4)=2*7+1=15。
• 第六题答案：B. 1次。最大圆盘在最优解中只需从起始柱直接移到目标柱一次。
• 第七题答案：B. 10。最少移动次数2^n-1=1023，解得2^n=1024，n=10。
  

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

FishC

a247863072 发表于 2026-06-04 18:49
@FishC 下列代码的输出结果是？

def is_even(n):
...

问题1： 代码输出是 False（选项B）。  
因为 is_odd(36) 会交替调用 is_even 和 is_odd，每次 n 减1，一直减到 n=0 时 is_odd(0) 返回 False。你不需要手动数36次，理解“偶数调用 is_odd 最终落在 is_odd(0)”即可。

问题2： len(plan(3, "左", "中", "右")) 输出是 7（选项C）。  
这是汉诺塔递归，移动次数公式为 2^n - 1，n=3 时是7步。你的“4+1+4”是错误理解，递归分解结果是 [(左→右), (左→中), (右→中), (左→右), (中→左), (中→右), (左→右)]，共7个。

问题3： 迭代手动模拟递归最常用的数据结构是 栈（Stack）（选项B）。  
因为递归本质就是函数调用栈，后进先出。

问题4： 写递归时当前层最应该做的是 A：只关心如何拆分子问题及用子问题结果完成当前任务。  
相信底层函数正确，把子问题当黑盒。

问题5： steps(4) 输出 15（选项C）。  
你推导正确：steps(4)=2*steps(3)+1，逐步计算得15，即 2^4 - 1。

问题6： 汉诺塔中最大圆盘只移动 1 次（选项B）。  
因为只需从起始柱直接搬到目标柱，中间过程它的位置一直没变。

问题7： 最少步数1023次对应圆盘数 10（选项B）。  
公式 2^n - 1 = 1023，解得 2^n = 1024，n=10。

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

FishC

a247863072 发表于 2026-06-04 18:49
@FishC 下列代码的输出结果是？

def is_even(n):
...

  
• 第一个问题：代码输出结果是 B. False。这是互递归判断奇偶性，is_odd(36) 表示 36 是偶数，故返回 False。无需手动数 36 次，理解原理即可。  
• 第二个问题：代码输出结果是 C. 7。函数 plan 实现汉诺塔最优移动序列，n=3 时总步数为 2^3 - 1 = 7。len(plan(3,...)) 即为 7。  
• 第三个问题：最常用的数据结构是 B. 栈（Stack）。递归调用本质是函数栈，手动模拟递归常用栈保存状态。  
• 第四个问题：在当前层最应该做的是 A。只关心如何拆分子问题并用子问题结果完成当前层任务，信任下一层能正确解决。  
• 第五个问题：代码输出结果是 C. 15。steps(4)=2*steps(3)+1=2*(2*steps(2)+1)+1=...=15，你算得正确。  
• 第六个问题：最大圆盘移动次数是 B. 1 次。最优解中最大盘只需从起始柱移动到目标柱一次。  
• 第七个问题：圆盘数 n 最可能是 B. 10。因为 2^10 - 1 = 1023。  
  

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

a247863072

第五个问题：代码输出结果是 C. 15。steps(4)=2*steps(3)+1=2*(2*steps(2)+1)+1=...=15，碰到这种我非要用手算一遍吗@FishC

FishC

a247863072 发表于 2026-06-04 18:53
第五个问题：代码输出结果是 C. 15。steps(4)=2*steps ...

第五个问题：代码输出结果是 C. 15。steps(4)=2*steps(3)+1=2*(2*steps(2)+1)+1=...=15，碰到这种我非要用手算一遍吗@FishC

哈哈，别慌～其实手算一遍递归恰恰是理解递归本质最直观的方法，就像看魔术揭秘一样。但是，如果代码已经写好了，你完全不需要每次都自己手算，计算机会帮你一步步展开的。  

对于这个steps(n)函数，它的递推关系是：  

1.   
   
2. steps(1) = 1  
   
3. steps(n) = 2 * steps(n-1) + 1  
   

复制代码

其实它有一个通项公式：  

1.   
   
2. steps(n) = 2^n - 1  
   

复制代码

验证一下：n=4时，2^4-1=16-1=15，完美匹配！所以以后遇到这种“2倍加1”的规律，直接套公式秒出答案，不用再手算递推了{:10_227:}。  

当然，如果你在写代码调试时，手动模拟前几次调用还是很有用的，能帮你快速发现逻辑bug。记住：手算是理解，公式是捷径，电脑是苦力，你只需要聪明地选择方法就行～

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

a247863072

问题2： len(plan(3, "左", "中", "右")) 输出是 7（选项C）。  
这是汉诺塔递归，移动次数公式为 2^n - 1，n=3 时是7步。你的“4+1+4”是错误理解，递归分解结果是 [(左→右), (左→中), (右→中), (左→右), (中→左), (中→右), (左→右)]，共7个。@FishC
这个你把它一步步写出来，我不懂

FishC

a247863072 发表于 2026-06-04 18:54
问题2： len(plan(3, "左", "中", "右")) 输出是 7（ ...

鱼油你好，我来一步步给你拆解 plan(3, "左", "中", "右") 的递归过程。先记住汉诺塔的规则：要把 n 个盘子从源柱移到目标柱，可以借助辅助柱。移动次数确实是 2^n - 1，n=3 时就是 7 步。下面我用递归树的方式把每一步写清楚。

定义：  
plan(n, source, auxiliary, target) 表示把 n 个盘子从 source 移到 target，辅助柱为 auxiliary。

递归基：  
当 n=1 时，直接移动：source → target。

递归步骤：  
对于 n≥2：  
1. 先把上面 n-1 个盘子从 source 移到 auxiliary（利用 target 做辅助）。  
2. 然后把最底下的大盘子从 source 移到 target。  
3. 最后把 n-1 个盘子从 auxiliary 移到 target（利用 source 做辅助）。

• 第一步： plan(3, "左", "中", "右")  
  因为 n=3>1，所以先做 plan(2, "左", "右", "中")  
  （把上面2个盘子从左→中，借助右）
  

• 第二步： plan(2, "左", "右", "中")  
  n=2>1，先做 plan(1, "左", "中", "右")  
  （把上面1个盘子从左→右，借助中）
  

• 第三步： plan(1, "左", "中", "右")  
  n=1，直接移动：左 → 右  【第1步】
  

• 第四步： plan(2,...) 的第二步：把剩余最大的盘子（左上的那个）从左移到中。  
  移动：左 → 中  【第2步】
  

• 第五步： plan(2,...) 的第三步：把刚才移到右的1个盘子再从中移到中。  
  注意：现在是 plan(1, "右", "左", "中")  
  n=1，直接移动：右 → 中  【第3步】
  

现在 plan(2, "左", "右", "中") 已完成，回到最外层。

• 第六步： plan(3,...) 的第二步：把最底下的大盘子从左移到右。  
  移动：左 → 右  【第4步】
  

• 第七步： plan(3,...) 的第三步：把已经在中柱上的2个盘子移到右柱（借助左柱）。  
  调用 plan(2, "中", "左", "右")
  

• 第八步： plan(2, "中", "左", "右")  
  先做 plan(1, "中", "右", "左")  
  n=1，直接移动：中 → 左  【第5步】
  

• 第九步： plan(2,...) 的第二步：把剩下的一个盘子（中柱上的）移到右。  
  移动：中 → 右  【第6步】
  

• 第十步： plan(2,...) 的第三步：把刚才移到左的盘子再从左移到右。  
  调用 plan(1, "左", "中", "右")  
  n=1，直接移动：左 → 右  【第7步】
  

全部结束，共7步。按顺序列出就是：

1. 
   
2. 左 → 右
   
3. 左 → 中
   
4. 右 → 中
   
5. 左 → 右
   
6. 中 → 左
   
7. 中 → 右
   
8. 左 → 右
   

复制代码

和你给出的列表完全一致。核心就是递归思想：先把上面两块移到中间，再移最底下那块到右，最后把中间两块移到右。希望对你有帮助！

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

a247863072

  不知道为什么
steps(1) = 1  
steps(n) = 2 * steps(n-1) + 1  
怎么得出这个通项公式的  
steps(n) = 2^n - 1  
@FishC

FishC

a247863072 发表于 2026-06-04 18:58
不知道为什么
steps(1) = 1  
steps(n) = 2 * steps ...

鱼油你好！ 这个问题其实是经典的“汉诺塔”递推关系。我们一步步推导：

已知：

• steps(1) = 1
• steps(n) = 2 × steps(n-1) + 1
  

两边同时加 1，得到：
steps(n) + 1 = 2 × steps(n-1) + 2 = 2 × (steps(n-1) + 1)

令 b(n) = steps(n) + 1 ，则上式变为：
b(n) = 2 × b(n-1)

同时， b(1) = steps(1) + 1 = 1 + 1 = 2 。

于是 b(n) 是首项为 2、公比为 2 的等比数列：
b(n) = 2 × 2^(n-1) = 2^n

最后， steps(n) = b(n) - 1 = 2^n - 1 。

所以通项公式 steps(n) = 2^n - 1 就得出来了。

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

wtr_2024

@FishC 在汉诺塔最优解中，“最大”的那个圆盘（最底下那片）会被移动几次？
A. n 次
B. 1 次
C. 2^(n-1) 次
D. 取决于 n 是奇数还是偶数

FishC

wtr_2024 发表于 2026-06-27 21:14
@FishC 在汉诺塔最优解中，“最大”的那个圆盘（最底 ...

根据汉诺塔的递归解法，要移动 n 个盘子，最优策略下最大的那个盘子（最底下的）只会被移动一次：从起始柱直接移动到目标柱。所以正确答案是 B. 1 次。

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