想象一下，你现在要给一个朋友讲一个“找东西”的故事。朋友问你：“这本书放在书架第几层？”你记不清具体位置，只记得它在书架的中间，但中间有很多层。这时候你可能会说：“我先问问最上层的人，他知道下面的位置吗？”不对，或许换个更简单的例子：递归就像你在解决一个问题时，发现“这个问题需要先解决两个更小的问题”，而这两个小问题和原来的问题是同类型的。
一、什么是递归？¶
递归的字面意思是“自己调用自己”，但更准确地说，它是一种将大问题分解成更小的同类问题，直到问题小到可以直接解决（称为“终止条件”），再通过小问题的结果反推大问题结果的方法。
举个生活化的例子：
你想知道班级里第10个同学的身高（假设已知班级所有人的身高），但你不记得具体是谁。于是你问：“第9个同学和第8个同学的身高分别是多少？”
第9个同学会问第8个和第7个，第8个同学会问第7个和第6个……直到你问到第1个同学（已知答案），然后逐层返回结果，最终算出第10个同学的身高。
二、斐波那契数列：递归的经典应用¶
斐波那契数列是一个非常经典的递归案例，它的定义很简单：
- 第0个数（F(0)）是0
- 第1个数（F(1)）是1
- 从第2个数开始，每个数等于前两个数之和：F(n) = F(n-1) + F(n-2)（n > 1）
比如：
F(0) = 0，F(1) = 1，F(2) = F(1)+F(0) = 1，F(3) = F(2)+F(1) = 2，F(4) = F(3)+F(2) = 3，F(5) = F(4)+F(3) = 5……
三、用递归计算斐波那契数列¶
我们用递归的思路来计算F(5)，看看它如何“分解”问题：
1. 终止条件：最小的问题¶
当n=0时，直接返回0；当n=1时，直接返回1。这两个是已知的基础情况，不需要再分解。
2. 递归条件：分解大问题¶
要计算F(n)，必须先计算F(n-1)和F(n-2)，然后把结果相加。
计算F(5)的步骤（从下往上）：¶
- 计算F(5) = F(4) + F(3)
- 计算F(4) = F(3) + F(2)
- 计算F(3) = F(2) + F(1)
- 计算F(2) = F(1) + F(0) = 1 + 0 = 1（终止条件）
- F(3) = F(2) + F(1) = 1 + 1 = 2（得到结果）
- F(4) = F(3) + F(2) = 2 + 1 = 3（得到结果）
- F(5) = F(4) + F(3) = 3 + 2 = 5（最终结果）
四、递归的核心：分解与终止¶
递归之所以“不绕”，是因为它遵循两个规则：
1. 终止条件：必须有明确的“不需要再分解”的情况（如F(0)和F(1)），否则会无限循环。
2. 问题规模递减：每次递归调用时，问题的规模都在变小（如n从5变成4和3，再变成更小的数），确保最终能到达终止条件。
五、递归的代码实现（Python举例）¶
用几行代码就能写出递归版本的斐波那契函数：
def fibonacci(n):
if n == 0: # 终止条件1：n=0时返回0
return 0
elif n == 1: # 终止条件2：n=1时返回1
return 1
else: # 递归条件：分解为两个小问题
return fibonacci(n-1) + fibonacci(n-2)
# 测试：计算F(5)
print(fibonacci(5)) # 输出：5
六、递归的小总结¶
递归就像“拆解任务”：
- 先把大问题切成两半“小问题”，直到小到能直接解决；
- 解决小问题后，再把结果合并成大问题的答案。
斐波那契数列的递归实现，用最简单的逻辑（分解+终止）解决了“大数字斐波那契数”的计算问题。虽然递归看起来“绕”，但它让代码更简洁，也体现了“以退为进”的智慧——先解决小问题，再解决大问题。
思考：如果不用递归，直接用循环计算斐波那契数（迭代法）会怎么样？你可以试试对比两种方法的差异，比如计算F(100)时递归会慢很多（为什么？），但递归的代码更短。这就是递归的“优雅”与“代价”。