递归(recursion)

要学好编程，递归是一个非常重要的概念，它能帮助你用优雅的方式解决很多问题。简单来说，递归就是函数自己调用自己来解决问题。听起来可能有点绕，但我们一步步来，通过具体的例子就能明白！

阶乘算法：从“按部就班”到“自我调用”

我们先从简单的阶乘说起。一个正整数的阶乘（比如 $5!$）是所有小于及等于该数的正整数的乘积。所以，$5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$。

递推（循环）实现阶乘

在了解递归之前，我们通常会用递推（也就是循环）的方式来计算阶乘。这就像你一步一步地完成任务：

#include <iostream> // 引入输入输出流库

// 全局使用 std 命名空间，方便后续代码编写
using namespace std; 

long long factorialIterative(int n) {
    long long result = 1; // 用 long long 防止数字太大溢出
    for (int i = 1; i <= n; ++i) {
        result *= i; // 每一步都把当前数字乘到结果上
    }
    return result;
}

int main() {
    cout << "5的阶乘 (递推): " << factorialIterative(5) << endl; // 输出: 120
    return 0;
}

这段代码很好理解：从 $1$ 循环到 $n$，每次都把 i 乘到 result 上，最终得到阶乘结果。

递归实现阶乘

现在，我们来看看更巧妙的递归版本。递归的关键在于找到两点：基本情况（Base Case）和递归关系（Recursive Relation）。

基本情况：当问题小到可以直接给出答案时。比如，在阶乘中，$0! = 1$ 或者 $1! = 1$。这是递归停止的“安全出口”，如果没有它，程序就会无限循环下去。
递归关系：如何把大问题拆解成一个小一点的、但形式相同的问题。你可以发现 $n! = n \times (n-1)!$。这意味着要算出 $n!$，我只需要知道 $(n-1)!$ 的结果就行了。

#include <iostream> // 引入输入输出流库

using namespace std; // 全局使用 std 命名空间

long long factorialRecursive(int n) {
    // 基本情况：当 n 是 0 或 1 时，直接返回 1
    if (n == 0 || n == 1) {
        return 1;
    }
    // 递归关系：n 的阶乘等于 n 乘以 (n-1) 的阶乘
    else {
        return n * factorialRecursive(n - 1); // 函数调用了自己！
    }
}

int main() {
    cout << "5的阶乘 (递归): " << factorialRecursive(5) << endl; // 输出: 120
    return 0;
}

当你调用 factorialRecursive(5) 时，它会去调用 factorialRecursive(4)，factorialRecursive(4) 又去调用 factorialRecursive(3)……一直到 factorialRecursive(1)。当 factorialRecursive(1) 返回 $1$ 后，结果就会像多米诺骨牌一样一层层地返回，最终 $5 \times 4 \times 3 \times 2 \times 1 = 120$。

汉诺塔问题：递归的“魔术”表演

汉诺塔是一个经典的递归问题，它能完美地展现递归的优雅和强大。问题是这样的：有三根柱子 A、B、C，A 柱上叠着 $n$ 个大小不一的圆盘，大盘在下，小盘在上。我们的目标是将所有圆盘从 A 柱移到 C 柱，每次只能移动一个圆盘，而且大盘不能放在小盘上面。

解决汉诺塔问题的递归思路非常简洁：

把顶部的 $n-1$ 个圆盘从 A 柱 移到 B 柱（借助 C 柱）。
把最底下的第 $n$ 个（最大的）圆盘从 A 柱 移到 C 柱。
把 B 柱上的 $n-1$ 个圆盘移到 C 柱（借助 A 柱）。

是不是有点像俄罗斯套娃？大的问题被分解成了一模一样的小问题！

#include <iostream> // 引入输入输出流库
#include <string>   // 引入字符串库

using namespace std; // 全局使用 std 命名空间

// n: 圆盘数量
// source: 源柱
// auxiliary: 辅助柱
// target: 目标柱
void hanoi(int n, char source, char auxiliary, char target) {
    // 基本情况：如果只有一个圆盘，直接移动
    if (n == 1) {
        cout << "将圆盘 1 从 " << source << " 移动到 " << target << endl;
        return;
    }
    // 1. 将 n-1 个圆盘从 source 移动到 auxiliary (借助 target)
    hanoi(n - 1, source, target, auxiliary);
    // 2. 将第 n 个圆盘从 source 移动到 target
    cout << "将圆盘 " << n << " 从 " << source << " 移动到 " << target << endl;
    // 3. 将 n-1 个圆盘从 auxiliary 移动到 target (借助 source)
    hanoi(n - 1, auxiliary, source, target);
}

int main() {
    cout << "移动 3 个圆盘的汉诺塔：" << endl;
    hanoi(3, 'A', 'B', 'C'); // 从 A 移到 C，B 是辅助
    return 0;
}

运行这段代码，你会看到详细的移动步骤。汉诺塔问题完美地展示了递归如何将一个看似复杂的问题，通过自我分解，最终简单明了地解决掉。

斐波那契数列：递推与递归的效率大比拼

斐波那契数列是一个有趣的数列，它的特点是每个数字都是前两个数字的和。数列的前几项是：$0, 1, 1, 2, 3, 5, 8, 13, \dots$。

递推（循环）实现斐波那契数列

递推方法通常是计算斐波那契数列的更高效方式：

#include <iostream> // 引入输入输出流库

using namespace std; // 全局使用 std 命名空间

long long fibonacciIterative(int n) {
    if (n <= 1) {
        return n;
    }
    long long a = 0; // 第 n-2 个数
    long long b = 1; // 第 n-1 个数
    for (int i = 2; i <= n; ++i) {
        long long temp = a + b; // 计算当前数
        a = b;                 // 更新 a 为上一个数
        b = temp;              // 更新 b 为当前数
    }
    return b;
}

int main() {
    cout << "斐波那契数列第 7 项 (递推): " << fibonacciIterative(7) << endl; // 输出: 13
    return 0;
}

时间复杂度分析（递推）：这段代码只用了简单的 for 循环，循环次数和 n 成正比。所以，它的时间复杂度是 $O(n)$。这意味着计算第 n 个斐波那契数所需的时间会随着 n 的增大而线性增长，非常高效。

递归实现斐波那契数列

斐波那契数列的递归定义是 $F(n) = F(n-1) + F(n-2)$，基本情况是 $F(0) = 0$，$F(1) = 1$。

#include <iostream> // 引入输入输出流库

using namespace std; // 全局使用 std 命名空间

long long fibonacciRecursive(int n) {
    if (n <= 1) {
        return n; // 基本情况：F(0)=0, F(1)=1
    } else {
        // 递归关系：F(n) = F(n-1) + F(n-2)
        return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
    }
}

int main() {
    cout << "斐波那契数列第 7 项 (递归): " << fibonacciRecursive(7) << endl; // 输出: 13
    // 尝试更大的 n 值，你会发现速度明显变慢，甚至卡住！
    // cout << "斐波那契数列第 40 项 (递归): " << fibonacciRecursive(40) << endl; 
    return 0;
}

时间复杂度分析（递归）：虽然这段递归代码看起来非常简洁和符合定义，但它的效率却非常低。为了计算 fibonacciRecursive(n)，它会分别计算 fibonacciRecursive(n-1) 和 fibonacciRecursive(n-2)。问题来了：fibonacciRecursive(n-1) 还会去计算 fibonacciRecursive(n-2) 和 fibonacciRecursive(n-3)。你看，fibonacciRecursive(n-2) 就被重复计算了！随着 n 增大，重复计算会越来越多，形成一个巨大的重复计算树。

这种重复计算导致了大量的冗余工作。斐波那契数列的朴素递归实现的时间复杂度大约是 $O(2^n)$，这是一种指数级的增长。这意味着 n 稍微大一点（比如 $n=40$），计算时间就会急剧增加，让你等得花儿都谢了。

总结：递推与递归，如何选择？

递推（循环）：通常效率更高，因为它避免了重复计算，并且没有函数调用的额外开销。时间复杂度通常是线性的（$O(n)$）或多项式的，性能稳定。
递归：代码可能更简洁、更符合直觉地表达某些算法（如汉诺塔）。但如果设计不当（如斐波那契数列的朴素递归），可能会导致大量的重复计算，从而效率低下。

那到底什么时候用递归呢？ 当问题本身具有天然的递归结构，而且递归能让代码更清晰、更易于理解时，就优先考虑递归。比如：遍历树形结构、图的深度优先搜索等。对于斐波那契数列这种有大量重复子问题的情况，如果非要用递归，通常会结合**记忆化（Memoization）或动态规划（Dynamic Programming）**来优化，避免重复计算，从而提高效率。

希望通过这些例子，你对递归有了初步的认识！它是一个非常强大且优雅的编程工具。在实际编程中多练习，你会越来越熟练地掌握它。你还有哪些关于递归或者其他编程概念的问题吗？