递归（Recursion）是一种通过函数调用自身来解决问题的方法。要正确设计和实现递归算法，必须满足 递归三要素，否则可能导致无限递归、栈溢出或逻辑错误。
递归的三个核心要素
1. 递归终止条件（Base Case）
-
作用：明确递归何时结束，防止无限调用。
-
要求：
- 必须有至少一个终止条件（即可以直接求解的简单情况）。
- 终止条件通常是问题的最小规模或边界条件。
-
示例（阶乘计算）：
def factorial(n):if n == 0: # Base Case: 0! = 1return 1return n * factorial(n - 1)
2. 递归调用（Recursive Case）
-
作用：将原问题分解为更小的同类子问题，通过调用自身解决。
-
要求：
- 每次递归调用必须向终止条件逼近（即问题规模减小）。
- 子问题的解能组合成原问题的解。
-
示例（斐波那契数列）：
def fibonacci(n):if n <= 1: # Base Case: fib(0)=0, fib(1)=1return nreturn fibonacci(n - 1) + fibonacci(n - 2) # Recursive Case
3. 问题可分解性（Progress Toward Base Case）
-
作用：确保每次递归调用后，问题规模严格缩小，最终达到终止条件。
-
要求：
- 递归调用的参数必须比原问题的参数更接近终止条件。
- 避免“原地递归”或扩大问题规模（否则会导致无限递归）。
-
错误示例（缺少问题规模缩小）：
def infinite_recursion(n):if n == 0:return 1return infinite_recursion(n) # 参数未改变，无限递归！
递归执行过程分析
以计算 factorial(3) 为例：
factorial(3)→3 * factorial(2)factorial(2)→2 * factorial(1)factorial(1)→1 * factorial(0)factorial(0)→ 返回1（终止条件）- 逐层返回结果：
1→1*1=1→2*1=2→3*2=6。
常见递归问题类型
- 分治问题（divide-and-conquer）（如归并排序、快速排序）。
- 树/图遍历（如二叉树的前序/中序/后序遍历）。
- 回溯算法（如八皇后问题、迷宫求解）。
注意事项
- 栈溢出风险：递归深度过大时（如数万层），需改用 尾递归优化 或 迭代。
- 重复计算问题：如斐波那契数列的朴素递归效率极低，需配合 备忘录（Memoization） 优化。
递归的核心在于 将大问题拆解为小问题，理解三要素后，可以更安全地设计递归算法。