21 · 递归：出口、递推与栈

把一个规模为 n 的问题，交给规模更小的同类问题去解决——这就是递归。它能停下来，只因为存在一个不需要再拆的小情形。

先看两个错法，它们分别代表递归的两类死法。

int f(int n) { return f(n - 1) + 1; }          // ① 没有出口

int g(int n) {                              // ② 有出口，但同一件事算了又算
    if (n <= 2) return 1;
    return g(n - 1) + g(n - 2);
}

① 的调用链 f(n) → f(n−1) → f(n−2) → …永不停，栈一直往下压，直到用完栈空间，程序收到 SIGSEGV（Windows 上是 0xC00000FD），评测判 RE。② 有出口，但 g(n−1) 展开时已经把 g(n−2)、g(n−3) 都算过一遍，外面又为 g(n−2) 把这一整批下标重新算一遍。调用次数是 φⁿ 级——g(40) 约 3×10⁸ 次，g(50) 到 4×10¹⁰ 次，判 TLE。小数据它跑得飞快，这才是最坑的地方。这个“重复计算”的毛病下一节用记忆化治。

这一节有三张卡要先看懂：递归函数长什么样、调用一次在内存里留下什么、assert 怎么帮你定位错误。

long long fact(int n) {              // 求 n!
    if (n <= 1) return 1;            // ① 出口：0! = 1! = 1
    return (long long)n * fact(n - 1);   // ② ③ n! = n × (n-1)!
}

int main() {
    cout << fact(5) << "\n";         // 120
    return 0;
}

long long fact(int n) {
    if (n <= 1) return 1;
    return (long long)n * fact(n - 1);   // 每层一帧
}

// fact(100000);   深度 10⁵，约 5MB，8MB 栈刚好够
// fact(1000000);  深度 10⁶，约 50MB，必 RE

long long fact(int n) {
    assert(n >= 0 && n <= 20);   // 21! 就超出 long long 了
    if (n <= 1) return 1;
    return (long long)n * fact(n - 1);
}

// fact(-1) → Assertion `n >= 0 && n <= 20' failed. 程序立刻停下

solve(1,1,3)                        涂 4×4，然后 3 个子调用
├─ solve(1,5,2)   右上        涂 2×2
│  ├─ solve(1,7,1)            涂 1 格
│  ├─ solve(3,5,1)
│  └─ solve(3,7,1)
├─ solve(5,1,2)   左下
│  ├─ solve(5,3,1)
│  ├─ solve(7,1,1)
│  └─ solve(7,3,1)
└─ solve(5,5,2)   右下
   ├─ solve(5,7,1)
   ├─ solve(7,5,1)
   └─ solve(7,7,1)

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1 << 10;         // 2^10 = 1024，n ≤ 10 时的最大边长
int a[MAXN + 5][MAXN + 5];       // 必须放全局：1024² 个 int = 4MB，放栈上直接炸
int N;                            // 边长 2^n

// 处理左上角 (x,y)、边长 2^k 的方块
void solve(int x, int y, int k) {
    assert(k >= 0);               // 调试用：k 不该变成负数
    if (k == 0) return;           // 出口：边长 1，没有可分的
    int h = 1 << (k - 1);         // 半边长 2^(k-1)
    for (int i = x; i < x + h; ++i)
        for (int j = y; j < y + h; ++j)
            a[i][j] = 0;          // 左上角那半块整体赦免

    solve(x + h, y,     k - 1);   // 右上块：行下移 h
    solve(x,     y + h, k - 1);   // 左下块：列右移 h
    solve(x + h, y + h, k - 1);   // 右下块：行、列都移 h
}

int main() {
    ios::sync_with_stdio(false);  // 最多 10⁶ 个数要输出，必须提速
    cin.tie(nullptr);

    int n; cin >> n;
    N = 1 << n;
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
            a[i][j] = 1;          // 先假设谁都没被赦免

    solve(1, 1, n);               // 只负责把该是 0 的格子涂成 0

    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
            cout << a[i][j] << (j == N ? '\n' : ' ');
    return 0;
}

同一件事换一种遍历顺序：递归是“先钻到底再回来”（深度优先），迭代可以“按块的大小从大到小”一层一层涂（宽度优先）。两种顺序结果相同，因为不同层的涂色位置互不重叠：被递归跳过的方块整块已经在上一层变成 0，再涂一遍也还是 0。

// 迭代版：把递归改成按层扫描，不写函数调用
for (int k = n; k >= 1; --k) {          // 块的大小从 2^n 降到 2
    int len = 1 << k, h = len >> 1;
    for (int x = 1; x + len - 1 <= N; x += len)
        for (int y = 1; y + len - 1 <= N; y += len)
            for (int i = x; i < x + h; ++i)
                for (int j = y; j < y + h; ++j)
                    a[i][j] = 0;
}

代价对比：递归版一共涂 4ⁿ − 3ⁿ = 989527 格（n = 10），迭代版把一些已经是 0 的格子又涂了一遍，共 2621440 次赋值，是前者的 2.65 倍。这点差别只是常数，不改变结论——换来的是彻底摆脱栈深度的限制，代价几乎为零。

        n
T(n) =  Σ  3^(n-k) · 4^(k-1)                 // 等比数列，公比 4/3
       k=1

     =  3^(n-1) · [1 + 4/3 + (4/3)^2 + … + (4/3)^(n-1)]

     =  3^(n-1) · ((4/3)^n − 1) / (4/3 − 1)

     =  4^n − 3^n

#include <bits/stdc++.h>
using namespace std;

// 输出 n 的表示，不含外层括号
void print(int n) {
    bool first = true;                 // 是不是第一个片段
    for (int i = 14; i >= 0; --i) {    // 20000 < 2^15，指数最大 14
        if ((n >> i) & 1) {            // 第 i 位是 1，说明要写 2^i
            if (!first) cout << "+";   // 加号只出现在片段之间
            first = false;

            if (i == 0)      cout << "2(0)";              // 特例：0 次幂
            else if (i == 1) cout << "2";                 // 特例：1 次幂
            else { cout << "2("; print(i); cout << ")"; }  // 一般情况：指数递归展开
        }
    }
}

int main() {
    int n; cin >> n;
    print(n);
    cout << "\n";
    return 0;
}