Day 16 · 递归入门：自己调用自己

题意：求 n! = 1 × 2 × 3 × … × n。题目额外加了一句挑战：尝试不使用循环语句（for、while）完成。

思路

这题就是第 2 节那个例子的原题，直接套三要素：

递归深度最大 12 层，完全不用担心栈的问题。

3

6

完整代码

#include <iostream>
using namespace std;

long long fact(int n) {
    if (n <= 1) return 1;              // 出口：0! = 1! = 1
    return (long long)n * fact(n - 1); // 递推关系：n! = n * (n-1)!
}

int main() {
    int n;
    cin >> n;
    cout << fact(n) << endl;
    return 0;
}

易错点

• 忘记写出口 —— 本题最经典的错误，会栈溢出。
• 递归时忘了把 n 减 1（写成 fact(n)）：参数永远不变，到不了出口。
• 返回类型用了 int 还真的去乘大数：本题 n ≤ 12 侥幸没事，但换成 13 就溢出了。用 long long。
• 出口写成 if(n == 0) return 1; 只处理 0 的情况：那 n = 1 时还会继续递归到 fact(0)，能对但多绕一层。写 n <= 1 最稳。

题意：小猴买了若干桃子。第一天吃掉这些桃子的一半再多一个，之后每天都吃掉当天剩余的一半再多一个。 到了第 n 天早上，只剩下 1 个桃子了。问：小猴一开始买了多少个桃子？

思路

正着推推不动（不知道第 1 天有多少），所以从最后一天往回倒推，推导过程见第 7 节：

三要素对照：

验算 n = 4：peaches(1) = 1 → peaches(2) = 4 → peaches(3) = 10 → peaches(4) = 22。

4

22

完整代码

#include <iostream>
using namespace std;

// 含义：如果第 n 天早上剩 1 个，那么第 1 天早上有多少个桃子
long long peaches(int n) {
    if (n == 1) return 1;                       // 出口：只过 1 天，剩的就是买的
    return (peaches(n - 1) + 1) * 2;            // 倒推：昨天 = (今天 + 1) * 2
}

int main() {
    int n;
    cin >> n;
    cout << peaches(n) << endl;
    return 0;
}

易错点

• 把 +1 写成 −1：最容易犯的错。「多吃一个」→ 剩下的比一半少 1 → 倒推时要先把 1 加回来。 用 n = 4 手算一遍立刻能发现。
• 循环/递归次数搞错：从第 n 天推回第 1 天，要推 n − 1 次，不是 n 次。 递归写法里这体现为 peaches(n-1) 一直推到 peaches(1)。
• 出口写成 n == 0：那 n = 1 时会去调 peaches(0)，算出 (1+1)×2 = 4，答案就错了。出口必须是 n == 1。
• 「一半」是整数除法：题目数据保证每天剩余的都是偶数，不用考虑除不尽的情况，但心里要有数。

题意：有 2ⁿ × 2ⁿ 个人站成方阵。每轮把正方形均分成四块，左上那一块的所有人全部赦免， 剩下三块各自继续做同样的事，直到方阵无法再分（只剩 1 个人）。输出每个人的命运：0 表示被赦免，1 表示不被赦免。

思路

标准的分治。先想清楚「函数在处理什么」：

三要素对照：

另外可以算一下工作量：递归树的节点数是 1 + 3 + 9 + … + 3n = (3n+1 − 1) / 2。 n = 10 时约 8.9 万个节点，每个节点只做 O(1) 的事 —— 非常快。递归深度只有 10 层，不会爆栈。

3

0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 1
0 0 0 0 0 1 0 1
0 0 0 0 1 1 1 1
0 0 0 1 0 0 0 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1

完整代码

#include <cstdio>

const int MAXN = 1030;
char a[MAXN][MAXN];                 // 全局数组自动全是 0（0 = 被赦免）

// 处理左上角为 (x,y)、边长为 size 的正方形
void solve(int x, int y, int size) {
    if (size == 1) {                // 出口：分到只剩一个人 → 没被赦免
        a[x][y] = 1;
        return;
    }
    int h = size / 2;
    // 左上那一块整体都是 0，不用管，直接跳过
    solve(x,     y + h, h);         // 右上
    solve(x + h, y,     h);         // 左下
    solve(x + h, y + h, h);         // 右下
}

int main() {
    int n;
    scanf("%d", &n);
    int size = 1 << n;              // 2 的 n 次方
    solve(1, 1, size);

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

易错点

• 出口写成 size == 0：这样 size = 1 时还会继续分，而 1/2 = 0，会无限递归下去 → 栈溢出。出口必须是 size == 1。
• 四个象限少调一块或多调一块：左上角那块不能递归（它已经被赦免了）。如果手滑把左上角也递归了，图案会全错。
• 三块子方阵的左上角坐标写错：记住边长是 h = size/2，所以右边那块是 (x, y+h)，下面那块是 (x+h, y)。
• 输出用 cout 且每个数都 endl：10⁶ 次刷新缓冲区，会明显变慢。用 putchar 或者至少用 '\n'。
• 行末多打空格：用 putchar(j == size ? '\n' : ' ') 就不会多。
• 数组要开够：char a[1030][1030] 约 1 MB。注意这是全局数组，如果写成 main 里的局部数组可能会有栈问题。

题意：给定正整数 n，按下面的方式构造数列：

1. 只有一个数 n 的数列是合法的；
2. 在一个合法数列的末尾加一个正整数，但这个数不能超过该数列最后一项的一半，得到一个新的合法数列。

问：一共有多少个合法的数列？

比如 n = 6，合法的数列有：6、6,1、6,2、6,3、6,2,1、6,3,1，共 6 个。

思路

设 f[x] = 「以 x 开头的合法数列有多少个」。

从 x 出发，末尾能接的第一个数 i 可以是 1 到 x/2 之间的任意正整数。
一旦接上了 i，后面还能接什么，就完全由 i 决定了 —— 而「以 i 开头的合法数列个数」正好就是 f[i]。

再加上「只有 x 自己」这一个数列，就得到递推式：

f[x] = 1 + f[1] + f[2] + ... + f[x/2]

因为右边只用到比 x 小的下标，所以可以从 x = 1 开始从小到大一路填表填到 n，不需要递归。

复杂度：外层 n 次，内层平均 x/2 次，总共约 n²/4 = 25 万次加法（n = 1000），实测 35 ms，非常轻松。

6

6

完整代码

#include <iostream>
using namespace std;

const int MAXN = 1005;
long long f[MAXN];               // ★ 答案能到 19 亿，必须 long long

int main() {
    int n;
    cin >> n;

    for (int x = 1; x <= n; x++) {
        f[x] = 1;                        // 只有 x 自己这一个数列
        for (int i = 1; i <= x / 2; i++) {
            f[x] += f[i];                // 后面接上所有以 i 开头的合法数列
        }
    }
    cout << f[n] << endl;
    return 0;
}

long long memo[1005];
bool vis[1005];

long long f(int x) {
    if (vis[x]) return memo[x];          // ★ 算过就直接取，不再往下递归
    vis[x] = true;
    long long r = 1;                     // 只有 x 自己
    for (int i = 1; i <= x / 2; i++) r += f(i);
    return memo[x] = r;                  // 存起来，下次直接用
}

int main() { int n; cin >> n; cout << f(n) << endl; return 0; }

long long f(int x){
    long long r = 1;
    for(int i = 1; i <= x/2; i++) r += f(i);   // 没有任何缓存
    return r;
}

易错点

• 用纯递归：逻辑对但复杂度是指数级，n = 1000 必 TLE。
• 用 int 存答案：n = 1000 的答案 1981471878 已经贴到 int 上限（2147483647）， 稍有不慎就溢出成负数。必须 long long。
• 忘了 f[x] = 1 这一句：会漏掉「只有 x 自己」那个数列，答案偏小。
• 内层循环上界写成 x-1 或 x/2 + 1：题目说「不能超过最后一项的一半」， 所以是 i <= x/2，整数除法自动向下取整。x = 1 时 1/2 = 0，循环一次都不执行 → f[1] = 1，正确。
• 数组开小：n 最大 1000，数组至少开 1001，开 1005 留点余量。