迭代与递归 — 有哪些权衡？

Question

迭代与递归 — 有哪些权衡？

IT Interview Practice · Accepted Answer

**迭代** 使用循环；**递归** 使用自调用。它们在功能上是等价的（用一种做的任何事都可以用另一种做），但在清晰度和成本上有所不同。

## 并排比较

```python
# Iterative sum: constant extra space
def sum_iter(n):
    total = 0
    for i in range(1, n + 1):
        total += i        # accumulate in a loop
    return total

# Recursive sum: uses the call stack
def sum_rec(n):
    if n == 0:
        return 0
    return n + sum_rec(n - 1)
```

## 比较

| 方面 | 迭代 | 递归 |
|--------|-----------|----------|
| 内存 | O(1) 额外空间 | O(depth) 栈空间 |
| 可读性 | 适合线性工作 | 适合树 / 分治法 |
| 风险 | 无限循环 | 栈溢出 |
| 速度 | 通常更快（无调用开销） | 每帧都有调用开销 |

## 何时使用哪种

- 对简单的线性遍历和栈深度可能很大时，使用 **迭代**。
- 当问题本质上是递归的（树、图、回溯）且深度有界时，使用 **递归**。

## 陷阱

深度递归存在栈溢出风险；当深度无界时，将热递归代码转换为迭代（通常使用显式栈）。

## 为什么这很重要

选择正确的风格可以保持代码既正确又易读。

递归使树和图的代码优雅，但了解其内存成本可以让你避免在深度输入上崩溃。

当面试官要求你"将其转换为迭代"时，这种权衡判断正是他们探究的内容。

方面	迭代	递归
内存	O(1) 额外空间	O(depth) 栈空间
可读性	适合线性工作	适合树 / 分治法
风险	无限循环	栈溢出
速度	通常更快（无调用开销）	每帧都有调用开销

并排比较

相关问题

比较

何时使用哪种

陷阱

为什么这很重要