递归CSP-J

💡 核心思想

递归是函数直接或间接调用自身的编程技巧。它的核心思想是：将大问题分解为结构相同的更小子问题，直到子问题足够小可以直接求解。每个递归都需要两个要素：递归边界（终止条件）和递推关系（如何缩小问题规模）。

🎯 直觉理解

想象俄罗斯套娃：要打开最外面的大套娃，你先得打开它，里面有个小一点的，再打开，一直开到最小的那个（终止条件）。然后你从最小的开始，把每层的结果组合起来。递归就是这样：一路拆到底，再一路组合回来。

📝 算法流程

1. 明确函数的语义：f(n) 代表什么？
2. 确定递归边界（base case）：最小的 n 时直接返回
3. 写出递推关系：f(n) 如何由 f(n-1) 或其他更小的子问题得到
4. 信任递归：假设子问题已经正确解决，只关注当前层

$$f(n) = \begin{cases} 1 & n = 0 \\ n \times f(n-1) & n > 0 \end{cases} \text{（阶乘示例）}$$

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
// 递归三要素示例

// 1. 阶乘：f(n) = n * f(n-1), f(0) = 1
long long factorial(int n) {
    if (n <= 1) return 1;        // 终止条件
    return n * factorial(n - 1);  // 递推关系
}

// 2. 斐波那契数列（朴素递归，仅作演示）
long long fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

// 3. 汉诺塔
void hanoi(int n, char from, char mid, char to) {
    if (n == 1) { cout << from << " -> " << to << "\n"; return; }
    hanoi(n-1, from, to, mid);   // 上面 n-1 个从 from 借 to 到 mid
    cout << from << " -> " << to << "\n"; // 最大的那个直接移
    hanoi(n-1, mid, from, to);   // n-1 个从 mid 借 from 到 to
}

int main() {
    cout << "5! = " << factorial(5) << endl;
    hanoi(3, 'A', 'B', 'C');
    return 0;
}

⚠️ 常见坑点

📚 相关题目