第049讲：函数（IX）- 递归

haly

@FishC 以下代码执行后，输出结果是什么？

def mystery(n):
    if n == 1:
        return 1
    mystery(n - 1)

print(mystery(3))

A. 1
B. 2
C. 3
D. None

FishC

haly 发表于 2026-04-03 05:47
@FishC 以下代码执行后，输出结果是什么？

def mys ...

这段代码的输出结果是 D. None。

原因在于函数 mystery 在递归调用时没有使用 return 语句来返回递归结果。具体分析如下：

1. 
   
2. def mystery(n):
   
3.     if n == 1:
   
4.         return 1
   
5.     mystery(n - 1)  # 这里没有 return 语句
   

复制代码

- 当调用 mystery(3) 时，因为 n 不等于 1，它会执行 mystery(2) 但不返回其值。
- 类似地，mystery(2) 执行 mystery(1) 也不返回其值。
- mystery(1) 返回 1，但这个返回值没有被传递回顶层调用。
- 由于函数在非终止条件分支中没有显式返回值，Python 会默认返回 None。

因此，print(mystery(3)) 输出 None。

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

haly

@FishC 在实际问题中，下列哪个场景通常更“天然”适合用递归来写？
A. 遍历文件夹及其所有子文件夹
B. 计算 1 到 n 的和
C. 把字符串全部转成大写
D. 打印九九乘法表

FishC

haly 发表于 2026-04-03 05:57
@FishC 在实际问题中，下列哪个场景通常更“天然”适 ...

遍历文件夹及其所有子文件夹是典型的递归应用场景，因为文件夹结构本身就是树状的，每个文件夹的处理方式相同（遍历子文件夹和文件）。其他选项虽然也可以用递归实现，但通常有更简单直观的迭代方法。

因此最“天然”适合递归的是：A. 遍历文件夹及其所有子文件夹

简单对比：

• A：文件夹结构是递归的（每个子文件夹又是一个文件夹），递归代码简洁自然。
• B：求和可以用递归，但直接用循环或公式更高效直观。
• C：字符串转大写只需简单遍历每个字符，递归反而复杂。
• D：九九乘法表通常用双重循环，递归并无优势。
  

示例代码（遍历文件夹）：

1. 
   
2. import os
   
3. 
   
4. def list_files(path):
   
5.     for item in os.listdir(path):
   
6.         full_path = os.path.join(path, item)
   
7.         if os.path.isdir(full_path):
   
8.             list_files(full_path)  # 递归处理子文件夹
   
9.         else:
   
10.             print(full_path)
    

复制代码

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

LaysPocky

哇，反应不过来

a247863072

@FishC 下列代码的输出顺序是？

def show(n):
    if n == 0:
        print("X")
    else:
        print("A" + str(n))
        show(n - 1)
        print("B" + str(n))

show(2)

A. A2→A1→X→B1→B2
B. A2→B2→A1→B1→X
C. X→A1→B1→A2→B2
D. A2→A1→B2→B1→X
不是到x就结束吗

@FishC 爬楼梯：每次可以走 1 阶或 2 阶（ways(n) 表示走到第 n 阶的走法数），请问下列代码执行后会输出多少？

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

print(ways(5))

A. 5
B. 8
C. 13
D. 16

一共递归了几次？

FishC

a247863072 发表于 2026-06-03 00:57
@FishC 下列代码的输出顺序是？

def show(n):
    ...

第一个问题：代码输出顺序是 A2→A1→X→B1→B2，对应选项A。递归调用在打印X后不会结束，而是返回上层继续执行后面的语句。

第二个问题：输出值为 8，对应选项B。  
递归总次数（包括初始调用）为 9 次。

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

FishC

a247863072 发表于 2026-06-03 00:57
@FishC 下列代码的输出顺序是？

def show(n):
    ...

第一个问题：代码输出顺序  
分析：show(2) 执行时，先打印 "A2"，然后调用 show(1)；show(1) 打印 "A1"，再调用 show(0)；show(0) 打印 "X" 后返回；回到 show(1) 继续执行，打印 "B1"；返回 show(2) 打印 "B2"。因此顺序是 A2 → A1 → X → B1 → B2，对应选项 A。  
注意：递归调用完成后，还会执行后面的 print("B" + str(n))，所以不会到 X 就结束。

第二个问题：ways(5) 的结果  
分析：ways(1)=1，ways(2)=2，ways(3)=ways(2)+ways(1)=3，ways(4)=ways(3)+ways(2)=5，ways(5)=ways(4)+ways(3)=8。输出为 8，对应选项 B。  

额外：递归次数统计  
递归次数指函数被调用的总次数（包括初始调用）。以 ways(5) 为例，调用树如下：  
- ways(5) 调用 1 次  
- ways(4) 调用 1 次  
- ways(3) 被调用 2 次（来自 ways(5) 和 ways(4)）  
- ways(2) 被调用 2 次（来自 ways(4) 和 ways(3)）  
- ways(1) 被调用 1 次（来自 ways(3)）  
总计调用次数 = 1+1+2+2+1 = 7 次。

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

a247863072

FishC 发表于 2026-6-3 00:57
第一个问题：代码输出顺序是 A2→A1→X→B1→B2，对应选项A。递归调用在打印X后不会结束，而是返回上层 ...

我不理解你把它每一步递归写出来，

FishC

a247863072 发表于 2026-06-03 00:59
FishC 发表于 2026-6-3 00:57
第一个问题：代码输出 ...

我理解你的疑惑。下面我把两个问题对应的递归执行过程一步一步写出来，这样你就能看清楚递归是怎么“去”又怎么“回”的。

---

### 问题1：`show(2)` 的详细执行过程（用【】表示输出）

1. 1. 调用 show(2)
   
2.    n=2，不满足 n==0，走 else 分支
   
3.    输出：【A2】
   
4.    调用 show(1) → 进入第2步
   
5. 
   
6. 2. 调用 show(1)
   
7.    n=1，不满足 n==0
   
8.    输出：【A1】
   
9.    调用 show(0) → 进入第3步
   
10. 
    
11. 3. 调用 show(0)
    
12.    n=0，满足 n==0
    
13.    输出：【X】
    
14.    函数结束，返回调用处（即第2步的 show(1) 内部）
    
15. 
    
16. 4. 回到 show(1)
    
17.    刚刚调用 show(0) 完成，接着执行下一行：print("B" + str(n))
    
18.    此时 n=1，输出：【B1】
    
19.    函数结束，返回调用处（即第1步的 show(2) 内部）
    
20. 
    
21. 5. 回到 show(2)
    
22.    刚刚调用 show(1) 完成，接着执行下一行：print("B" + str(n))
    
23.    此时 n=2，输出：【B2】
    
24.    函数结束，返回 print(mystery(3)) 所在的最外层

复制代码

所以依次输出的结果是：  
**A2 → A1 → X → B1 → B2**（对应选项A）

**为什么不是到X就结束？**  
因为递归可以理解成“先去深处，再逐层返回”。`show(0)` 打印 X 后确实立即结束，但结束的是最里层的那一次调用，它会把控制权交还给上一层的 `show(1)`，而 `show(1)` 在打印完 A1、调用 `show(0)` 后，还有一句 `print("B1")` 等着执行，所以一定会继续打印 B1，同理再返回上一层打印 B2。

---

### 问题2：`ways(5)` 的递归调用展开（计算总递归次数）

`ways(5)` 的递推关系：  
- ways(1) = 1  
- ways(2) = 2  
- ways(n) = ways(n-1) + ways(n-2)

我们画出递归调用树（每个节点代表一次函数调用，包括计算叶子节点的过程）：

1. ways(5)
   
2.                                 /       \
   
3.                            ways(4)      ways(3)
   
4.                           /      \      /     \
   
5.                      ways(3)   ways(2) ways(2) ways(1)
   
6.                     /    \       |       |       |
   
7.                ways(2) ways(1)   2       2       1
   
8.                  |       |
   
9.                  2       1

复制代码

**每一次调用（包括那些直接返回1或2的叶子调用）都算一次递归。**  
我们数一下所有节点个数：

- 第1层：ways(5) → 1个  
- 第2层：ways(4), ways(3) → 2个  
- 第3层：ways(3), ways(2), ways(2), ways(1) → 4个  
- 第4层：ways(2), ways(1) → 2个  
（注意：第3层的第一个ways(3)又产生了第4层的两个调用）

所以总调用次数 = 1 + 2 + 4 + 2 = **9次**。

最终 `print(ways(5))` 输出的是 **8**，即选项B。

---

希望这样一步一步的展开能帮助你彻底理解递归的执行流程。如果还有不清楚的地方，欢迎继续追问！

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