递归与迭代

在编程中，我们经常需要解决一些重复性的问题，比如计算阶乘、遍历数据结构、或者解决复杂的数学问题。对于这类问题，我们通常有两种基本的解决思路：递归和迭代。

想象一下，如果你要数一摞书有多少本，你可以：

• 方法一：从第一本开始，一本一本往下数，直到最后一本（迭代思维）
• 方法二：如果只有一本书，答案就是1；如果有很多本书，那么总数就是 1 本（最上面这本）+ 剩下这摞书的数量 n。而"剩下这摞书的数量"又是和之前是同样的问题，可以用同样的方法解决，即 1 本 + 继续剩下的书的数量。重复上述过程，直到最后变为 1 本 + 剩下书的数量为 1 本 的时候结束（递归思维）

这两种思维方式就对应着编程中的迭代和递归。让我们来深入了解它们。

递归

递归（Recursion）是指函数 在自身内部调用自己 。递归通常用于解决那些可以被分解为更小的同类问题的任务，比如数学上的递归定义、树结构遍历等。

递归的核心思想是：把大问题分解为小问题，直到遇到最简单的情况（递归终止条件）。

以阶乘为例，阶乘的数学定义如下：

用递归的概念来表示就是：

我们可以使用下面的代码来实现阶乘：

#include <iostream>
using namespace std;

int factorial_rec(int n) {
    if (n == 1) return 1;
    return n * factorial_rec(n - 1);
}

int main() {
    int n;
    cin >> n;
    cout << n << "! = " << factorial_rec(n) << endl;
    return 0;
}

在这个例子中，factorial_rec 函数会不断调用自己，直到 n 等于 1 时返回 1，然后逐次返回 $1 \times 2$、$1 \times 2 \times 3$、...、$1 \times 2 \times 3 \times \dots \times n$。

递归函数一般包含两个部分：

1. 递归终止条件（Base Case）：防止无限递归，必须有一个明确的出口。
2. 递归调用（Recursive Case）：函数调用自身，处理更小规模的问题。

如果没有终止条件，递归会无限进行下去，导致程序崩溃（栈溢出）。

迭代

迭代（Iteration）指的是通过循环语句（如 for、while 等）反复执行某段代码，直到满足某个条件为止。

还是以阶乘为例，我们可以用迭代来实现：

#include <iostream>
using namespace std;

int factorial_iter(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

int main() {
    int n;
    cin >> n;
    cout << n << "! = " << factorial_iter(n) << endl;
    return 0;
}

在这个例子中，我们用 for 循环从 1 累乘到 n，得到阶乘结果。

应用

递归和迭代在很多算法和数据结构中都有应用，比如：

• 斐波那契数列
• 二叉树遍历
• 汉诺塔问题
• 快速排序、归并排序

例如，斐波那契数列的递归实现：

int fib(int n) {
    if (n == 1 || n == 2) return 1;
    return fib(n - 1) + fib(n - 2);
}

同样的，迭代也可以实现这段代码：

int fib(int n) {
    if (n == 1 || n == 2) return 1;
    int a = 1, b = 1, c;
    for (int i = 3; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

实际上，从理论上来讲，所有递归能实现的，用迭代也能实现。只不过就如上述的斐波那契数列的实现一样，迭代在某些问题上看上去会比递归更加复杂。在实际编程中，选择递归还是迭代，要根据问题的特点和实际需求来决定。