递归函数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（计算速度大幅提升）