什么是递归？

Question

什么是递归？

Accepted Answer

**递归**是指函数调用自身来解决同一问题的更小版本。每个递归都需要一个**基本情况**来停止递归，以及一个**递归情况**来逼近基本情况。

## 核心思想

将问题分解为较小的相同子问题。每次调用都会在**调用栈**上压入一个栈帧；返回时则弹出。

## 示例

```python
def factorial(n):
    if n <= 1:            # base case: stop recursing
        return 1
    return n * factorial(n - 1)   # recursive case: smaller problem

factorial(4)             # 4 * 3 * 2 * 1 -> 24
```

## 追踪

```text
factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * 3 * 2 * 1 = 24
```

## 复杂度

此处**O(n)**时间和**O(n)**栈空间（每次调用一个栈帧）。

## 陷阱

- **缺少基本情况** -> 无限递归 -> 栈溢出。
- 深度递归会耗尽栈空间；某些语言缺少尾调用优化。
- 重复计算重叠子问题可能导致指数时间复杂度（通过记忆化修复）。

## 为什么这很重要

递归自然地表达自相似问题——树、图、分治法——远比循环更清晰。

它是归并排序、回溯和动态规划的思想基础。

理解调用栈还能让你更好地进行调试和内存推理。