递归算法设计与实现

递归（Recursion）是一种通过函数调用自身来解决问题的方法。要正确设计和实现递归算法，必须满足 递归三要素，否则可能导致无限递归、栈溢出或逻辑错误。

---

递归的三个核心要素

1. 递归终止条件（Base Case）

• 作用：明确递归何时结束，防止无限调用。
  
• 要求：
  • 必须有至少一个终止条件（即可以直接求解的简单情况）。
    
  • 终止条件通常是问题的最小规模或边界条件。
    
• 示例（阶乘计算）：
  

  def factorial(n):
      if n == 0:  # Base Case: 0! = 1
          return 1
      return n * factorial(n - 1)

---

2. 递归调用（Recursive Case）

• 作用：将原问题分解为更小的同类子问题，通过调用自身解决。
  
• 要求：
  • 每次递归调用必须向终止条件逼近（即问题规模减小）。
    
  • 子问题的解能组合成原问题的解。
    
• 示例（斐波那契数列）：
  

  def fibonacci(n):
      if n <= 1:  # Base Case: fib(0)=0, fib(1)=1
          return n
      return fibonacci(n - 1) + fibonacci(n - 2)  # Recursive Case

---

3. 问题可分解性（Progress Toward Base Case）

• 作用：确保每次递归调用后，问题规模严格缩小，最终达到终止条件。
  
• 要求：
  • 递归调用的参数必须比原问题的参数更接近终止条件。
    
  • 避免“原地递归”或扩大问题规模（否则会导致无限递归）。
    
• 错误示例（缺少问题规模缩小）：
  

  def infinite_recursion(n):
      if n == 0:
          return 1
      return infinite_recursion(n)  # 参数未改变，无限递归！

---

递归执行过程分析

以计算 factorial(3) 为例：
1. factorial(3) → 3 * factorial(2)
2. factorial(2) → 2 * factorial(1)
3. factorial(1) → 1 * factorial(0)
4. factorial(0) → 返回 1（终止条件）
5. 逐层返回结果：1 → 1*1=1 → 2*1=2 → 3*2=6。

---

常见递归问题类型

1. 分治问题（如归并排序、快速排序）。
   
2. 树/图遍历（如二叉树的前序/中序/后序遍历）。
   
3. 回溯算法（如八皇后问题、迷宫求解）。

---

注意事项

• 栈溢出风险：递归深度过大时（如数万层），需改用 尾递归优化 或 迭代。
  
• 重复计算问题：如斐波那契数列的朴素递归效率极低，需配合 备忘录（Memoization） 优化。

递归的核心在于 将大问题拆解为小问题，理解三要素后，可以更安全地设计递归算法。