递归与迭代的关系

学习目标

本节学习递归与迭代的关系。

递归和迭代都可以表示重复过程。递归通过函数调用自己推进问题，迭代通过循环不断更新状态。很多问题既可以用递归写，也可以用循环写。关键不是哪种方式永远更好，而是选择更适合表达问题结构的方式。

---

用递归计算求和

先看递归写法：

C++

int sumRecursive(int n) {
    if (n == 0) {
        return 0;
    }

    return sumRecursive(n - 1) + n;
}

Java

int sumRecursive(int n) {
    if (n == 0) {
        return 0;
    }

    return sumRecursive(n - 1) + n;
}

Python

def sum_recursive(n):
    if n == 0:
        return 0

    return sum_recursive(n - 1) + n

C#

int SumRecursive(int n)
{
    if (n == 0)
    {
        return 0;
    }

    return SumRecursive(n - 1) + n;
}

这个写法强调“前 $n$ 项和等于前 $n - 1$ 项和加上 $n$”。它的表达接近数学定义。

---

用迭代计算求和

同一个问题也可以用循环实现：

C++

int sumIterative(int n) {
    int total = 0;

    for (int i = 1; i <= n; i++) {
        total += i;
    }

    return total;
}

Java

int sumIterative(int n) {
    int total = 0;

    for (int i = 1; i <= n; i++) {
        total += i;
    }

    return total;
}

Python

def sum_iterative(n):
    total = 0

    for i in range(1, n + 1):
        total += i

    return total

C#

int SumIterative(int n)
{
    int total = 0;

    for (int i = 1; i <= n; i++)
    {
        total += i;
    }

    return total;
}

这个写法强调“从 1 加到 $n$”。它使用一个变量保存当前结果，不需要不断调用函数。

---

时间和空间对比

对于求和问题，递归和迭代的时间复杂度通常都是 $O(n)$，因为都需要处理从 1 到 $n$ 的数字。

但空间复杂度不同：

• 递归版本需要调用栈，额外空间通常是 $O(n)$。
• 迭代版本只使用固定变量，额外空间通常是 $O(1)$。

因此，在简单线性重复问题中，迭代通常更节省空间。

---

递归更适合表达什么问题

递归更适合表达天然具有层级或分裂结构的问题。

例如：

• 树的遍历。
• 图的深度优先搜索。
• 归并排序。
• 快速排序。
• 分治问题。
• 回溯搜索。

这些问题往往不是简单地“从 1 循环到 n”，而是一个问题会拆出一个或多个子问题。递归可以直接表达这种结构。

---

迭代更适合表达什么问题

迭代更适合简单、线性的重复过程。

例如：

• 遍历数组。
• 统计元素个数。
• 累加求和。
• 顺序查找。
• 固定次数循环。

这类问题用循环更直接，也通常更节省调用栈空间。

---

递归和迭代可以相互转换

很多递归可以改写成迭代。反过来，很多循环也可以用递归表达。

例如，递归调用栈可以用显式栈模拟。树的递归遍历，也可以用手动维护的栈改写成迭代版本。

这说明递归和迭代不是完全对立的。它们只是表达重复过程的不同方式。

---

本节小结

递归和迭代都能表示重复，但表达重点不同。

递归适合描述问题拆解和层级结构，代码往往更接近问题定义；迭代适合描述线性重复，通常更节省空间。选择递归还是迭代，应根据问题结构、代码清晰度和空间成本综合判断。