递归函数Recursive Function
递归函数（Recursive Function）是在函数内部直接或间接调用自身的函数，其核心思想是将问题分解为更小的子问题，直到达到终止条件（基例）。递归的本质是数学归纳法的编程实现。
递归的三要素
1.基例（base Case）
递归的终止条件，避免无限递归；
通常是问题的最简形式（如n == 0）。
2.递归步骤（Recursive Step）
将问题分解为更小的子问题；
调用自身处理子问题。
3.参数传递
通过参数将问题规模逐步缩小
经典递归示例
1.阶乘函数（Factorial）
def factorial(n): # 基例：0的阶乘是1 if n == 0: return 1 # 递归步骤：n! = n × (n-1)! return n * factorial(n-1) print(factorial(5)) # 输出：120（5×4×3×2×1）2.斐波那契数列（Fibonacci）
def fibonacci(n): # 基例：F(0)=0, F(1)=1 if n <= 1: return n # 递归步骤：F(n) = F(n-1) + F(n-2) return fibonacci(n-1) + fibonacci(n-2) print(fibonacci(6)) # 输出：8（0,1,1,2,3,5,8）3.字符串反转
def reverse_string(s): # 基例：空字符串直接返回 if len(s) == 0: return s # 递归步骤：取最后一个字符 + 反转剩余部分 return s[-1] + reverse_string(s[:-1]) print(reverse_string("hello")) # 输出：olleh递归与迭代的对比
| 特性 | 递归 | 迭代 |
|---|---|---|
| 代码行数 | 简洁（无需循环） | 通常较多（需循环和状态管理） |
| 空间复杂度 | 高（每次递归调用增加栈帧） | 低（仅需固定内存） |
| 时间复杂度 | 可能重复计算（如斐波那契） | 通常更优 |
| 可读性 | 直观（问题天然递归结构） | 需循环逻辑设计 |
递归的常见应用场景
1.树结构遍历：
前序/中序/后序遍历二叉树
class TreeNode: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right def inorder_traversal(root): if root: inorder_traversal(root.left) print(root.val) inorder_traversal(root.right)2.分治算法：
快速排序，归并排序的递归实现
3.数学问题：
幂运算（如pow（x，n）= x * pow（x，n-1））
4.动态规划：
记忆化递归优化（用缓存存储中间结果）
递归的注意事项
1.基例必须存在：
def infinite_recursion(): infinite_recursion() # 错误：无基例，导致栈溢出2.参数必须趋近基例：
def bad_factorial(n): if n == 0: return 1 return bad_factorial(n+1) # 错误：参数不趋近基例3.栈溢出风险：
def deep_recursion(n): if n == 0: return deep_recursion(n+1) # 递归深度无限增长4.重复计算问题：
斐波那契递归实现中，fib（5）会重复计算fib（3），fib（2）等；
解决方案：使用记忆化递归（Memoization）。
记忆化递归优化：通过缓存中间结果，避免重复计算
from functools import lru_cache @lru_cache(maxsize=None) def fibonacci(n): if n <= 1: return n return fibonacci(n-1) + fibonacci(n-2) print(fibonacci(30)) # 输出：832040（计算速度大幅提升）