信息学奥赛进阶：递归、枚举与贪心算法入门

递归是一个函数在自己内部调用自己。听起来绕，但它的本质是把一个大问题拆成一个规模更小的同类型问题。

最经典的例子是求阶乘：5! = 5 × 4 × 3 × 2 × 1。我们可以定义：fact(n) = n × fact(n-1)，出口是 fact(1) = 1。

int fact(int n) {
    if (n == 1) return 1;   // 出口条件
    return n * fact(n - 1); // 递归调用
}

当你调用 fact(5)，它会先调用 fact(4)，fact(4) 又调用 fact(3)，一路到 fact(1) 返回 1，再一层层乘回去，最终得到 120。

写递归的关键是两件事：出口条件（什么时候不再调用自己）和递推关系（大问题怎么拆成小问题）。缺了出口，程序会无限递归直到崩溃。

斐波那契数列：1、1、2、3、5、8、13……每一项等于前两项之和。递归写法：

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

这段代码非常简洁，但有性能问题：fib(5) 会调用 fib(4) 和 fib(3)，fib(4) 又会调用 fib(3) 和 fib(2)，fib(3) 被重复计算了。当 n 到 40 以上，计算时间会爆炸。这是递归的代价，以后学动态规划就是为了解决这个问题。

汉诺塔是另一个经典递归题：三根柱子，把 N 个盘子从 A 移到 C，大盘不能压小盘。解法思路：先把上面 N-1 个盘子从 A 移到 B，再把最底下的大盘从 A 移到 C，最后把 N-1 个盘子从 B 移到 C。

void hanoi(int n, char from, char aux, char to) {
    if (n == 1) {
        cout << from << " -> " << to << endl;
        return;
    }
    hanoi(n - 1, from, to, aux);
    cout << from << " -> " << to << endl;
    hanoi(n - 1, aux, from, to);
}

孩子不用看懂这个移动顺序为什么对，只要能理解"把 N 个盘子的问题拆成 N-1 个盘子的子问题"这个递归结构，就掌握了递归的精髓。

枚举的思想很朴素：把所有可能的情况全部列出来，一个一个验证，符合条件的就是答案。它不需要聪明的算法，只需要耐心和正确的循环嵌套。

举个例子：找出 100 以内所有的素数。素数是只能被 1 和自己整除的数。最直接的写法：

for (int i = 2; i <= 100; i++) {
    bool isPrime = true;
    for (int j = 2; j * j <= i; j++) {
        if (i % j == 0) {
            isPrime = false;
            break;
        }
    }
    if (isPrime) cout << i << " ";
}

外层循环枚举每个候选数 i，内层循环用 j 从 2 试到根号 i，看 i 能不能被 j 整除。如果都不能，i 就是素数。

枚举的核心是判断数据规模：题目给的 N 是多少？1 秒内能跑多少次？根据这个决定能不能暴力枚举。

经典题：公鸡 5 元一只，母鸡 3 元一只，小鸡 3 只 1 元。用 100 元买 100 只鸡，各买多少只？

for (int rooster = 0; rooster <= 20; rooster++) {
    for (int hen = 0; hen <= 33; hen++) {
        int chick = 100 - rooster - hen;
        if (chick < 0) continue;
        if (5 * rooster + 3 * hen + chick / 3.0 == 100
            && chick % 3 == 0) {
            cout << rooster << " " << hen << " " << chick << endl;
        }
    }
}

外层循环枚举公鸡数量（最多 20 只），内层枚举母鸡数量（最多 33 只），小鸡数量自动算出，再验证钱数是否等于 100。这就是典型的多重循环枚举。

再进阶：全排列——把 1 到 N 的所有排列全部列出来。N=3 时有 6 种：123、132、213、231、312、321。这种题用递归枚举最方便：第一个位置选哪个数，剩下的再递归排列。