递归算法是一种直接或间接地调用自身来解决问题的方法。它通过将原问题分解为规模更小、结构相同的子问题，并利用子问题的解来构造原问题的解。
递归算法 ≠ 递归函数
递归函数是编程语言的实现手段，而递归算法是更宏观的解题策略。比如，汉诺塔问题、归并排序、快速排序、回溯搜索等，都是典型的递归算法。
核心要素
任何一个正确的递归算法都必须包含以下三个要素：
| 要素 | 说明 |
|---|---|
| 1. 明确的子问题结构 | 原问题如何划分为一个或多个子问题，子问题与原问题形式相同。 |
| 2. 递推关系 | 子问题的解如何合并得到原问题的解。 |
| 3. 边界条件 | 问题规模小到可以直接求解，不再递归。 |
这三个要素缺一不可。缺少边界条件 → 无限递归；缺少递推关系 → 无法得到解；子问题结构不正确 → 算法错误。
适用条件
并不是所有问题都适合递归算法。通常，满足以下条件的问题更容易用递归设计：
- 问题可以分解为规模更小的同类子问题（自相似性）。例如：汉诺塔、斐波那契、树的遍历。
- 子问题之间相互独立（除了分治算法，回溯中可能有依赖，但总体上是递归探索）。比如归并排序的左右两半独立排序。
- 子问题的解可以高效合并，且合并代价不高。
- 问题边界清晰，容易定义。
执行过程分析
递归算法的执行可以分为两个阶段：
- 递推阶段：从原问题出发，不断缩小问题规模，直到达到边界条件。这个过程相当于向下展开。
- 回归阶段：从边界条件开始，逐层返回，利用子问题的解构造上一层问题的解。这个过程相当于向上回溯。
复杂度分析
时间复杂度 通用方法：递归树 + 主定理
对于分治型的递归算法，其时间复杂度通常满足递推式：
其中：
- a 是子问题个数
- b 是每次缩小的倍数
- f(n) 是合并/分解的代价
竞赛中常用实例：
- 归并排序：
- 二分查找：
- 朴素斐波那契：（指数级，不可接受）
空间复杂度
递归算法会使用调用栈，空间复杂度通常包含两部分：
- 递归深度对应的栈空间（最坏情况）
- 算法本身额外分配的空间（如归并排序的临时数组）
总结
递归算法的核心在于利用问题本身的自相似性，用简洁的方式描述复杂过程。它不仅是编程技巧，更是一种解决问题的数学思维。
- 优势：代码简洁，逻辑清晰，特别适合树、图、分治、回溯类问题。
- 劣势：可能存在重复计算和栈空间开销，需要视情况优化。
- 竞赛策略：优先用递归设计算法原型，再根据需要改写成迭代或添加记忆化。