递归函数

递归函数的定义、执行过程与边界条件。

概念

递归函数在定义中调用自身，每展开一层就要保存当前状态，直到触及边界条件（base case）才逐层返回。正确递归必须：问题规模每次向边界靠近，且边界有明确返回值。与 cspj.cpp.function 的区别：递归强调自调用与展开/回溯过程。与 cspj.algo.recurrence-and-recursion 的区别：后者偏递推关系与算法设计，这里偏语言层面的递归函数执行。CSP-J 初赛几乎每年阅读程序都有递归 trace（阶乘、Fibonacci、自定义递归）；2024 年同一卷上递归题密度尤其高。

CSP-J 常考

cspj-r1-2024 第 27–32、38、40–42 题：阅读与完善程序多题，跟踪递归调用次数、返回值或填空补边界/递归式。
cspj-r1-2019 第 28–29、32–37 题：阅读判断与完善程序，递归函数在某输入下的输出或空位选项。
cspj-r1-2025 第 3、19 题：单选与阅读，考查递归深度或返回值。
cspj-r1-2020 第 28–29 题：阅读程序判断递归终止与返回路径。

int fact(int n) {
    if (n <= 1) return 1;       // 边界
    return n * fact(n - 1);
}
int main() {
    cout << fact(5) << endl;      // 120
}

易错点

缺少边界或边界不可达会导致无限递归，阅读题问「是否一定终止」要看参数是否严格向边界变化。
同一表达式里多次调用递归（如 f(n-1) + f(n-1)）与 f(n-1) + f(n-2) 调用次数差很多，手 trace 时画调用树比心算可靠。
完善程序空位常考 return 后的递归式或 if (n == 0) 边界，勿与循环变量更新混淆。

阅读程序共 1.5 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

原卷作答说明：判断题正确填 √，错误填 ×

程序

#include <iostream>using namespace std;const int maxn = 10000;int n;int a[maxn];int b[maxn];int f(int l, int r, int depth) { if (l > r) return 0; int min = maxn, mink; for (int i = l; i <= r; ++i) { if (min > a[i]) { min = a[i]; mink = i; } } int lres = f(l, mink - 1, depth + 1); int rres = f(mink + 1, r, depth + 1); return lres + rres + depth * b[mink];}int main() { cin >> n; for (int i = 0; i < n; ++i) cin >> a[i]; for (int i = 0; i < n; ++i) cin >> b[i]; cout << f(0, n - 1, 1) << endl; return 0;}

28判断1.5 分
如果 $a$ 数组有重复的数字，则程序运行时会发生错误。（）

阅读程序共 1.5 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

原卷作答说明：判断题正确填 √，错误填 ×

程序

29判断1.5 分
如果 $b$ 数组全为 $0$ ，则输出为 $0$ 。（）

阅读程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

程序

32单选3 分
当 $n=10$ 时，若 $b$ 数组满足，对任意 $0\leq i<n$ ，都有 b[i] = i + 1，那么输出最大为（）。

A
386

B
383

C
384

D
385

阅读程序共 4 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

程序

33单选4 分
（4分）当 $n=100$ 时，若 $b$ 数组满足，对任意 $0 \leq i < n$ ，都有 b[i]=1，那么输出最小为（）。

A
582

B
580

C
579

D
581

完善程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

1.（矩阵变幻）有一个奇幻的矩阵，在不停的变幻，其变幻方式为：

数字 $0$ 变成矩阵

0 0 
0 1

数字 $1$ 变成矩阵

1 1
1 0

最初该矩阵只有一个元素 $0$ ，变幻 $n$ 次后，矩阵会变成什么样？

例如，矩阵最初为： $[0]$ ；

矩阵变幻 $1$ 次后：

0 0 
0 1

矩阵变幻 $2$ 次后：

输入一行一个不超过 $10$ 的正整数 $n$ 。输出变幻 $n$ 次后的矩阵。

试补全程序。

提示：

<< 表示二进制左移运算符，例如 $(11)_2$ << $2 = (1100)_2$ ；
而 ^ 表示二进制异或运算符，它将两个参与运算的数中的每个对应的二进制位—进行比较，若两个二进制位相同，则运算结果的对应二进制位为 $0$ ，反之为 $1$ 。

#include <cstdio>
using namespace std;
int n;
const int max_size = 1 << 10;

int res[max_size][max_size];

void recursive(int x, int y, int n, int t) {
    if (n == 0) {
        res[x][y] = ①;
        return;
    }
    int step = 1 << (n - 1);
    recursive(②, n - 1, t);
    recursive(x, y + step, n - 1, t);
    recursive(x + step, y, n - 1, t);
    recursive(③, n - 1, !t);
}

int main() {
    scanf("%d", &n);
    recursive(0, 0, ④);
    int size = ⑤;
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++)
            printf("%d", res[i][j]);
        puts("");
    }
    return 0;
}

程序

#include <cstdio>using namespace std;int n;const int max_size = 1 << 10;int res[max_size][max_size];void recursive(int x, int y, int n, int t) { if (n == 0) { res[x][y] = ①; return; } int step = 1 << (n - 1); recursive(②, n - 1, t); recursive(x, y + step, n - 1, t); recursive(x + step, y, n - 1, t); recursive(③, n - 1, !t);}int main() { scanf("%d", &n); recursive(0, 0, ④); int size = ⑤; for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) printf("%d", res[i][j]); puts(""); } return 0;}

34（①）单选空位 ①3 分
①处应填（）

A
n%2

B
0

C
t

D
1

完善程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

1.（矩阵变幻）有一个奇幻的矩阵，在不停的变幻，其变幻方式为：

数字 $0$ 变成矩阵

0 0 
0 1

数字 $1$ 变成矩阵

1 1
1 0

最初该矩阵只有一个元素 $0$ ，变幻 $n$ 次后，矩阵会变成什么样？

例如，矩阵最初为： $[0]$ ；

矩阵变幻 $1$ 次后：

0 0 
0 1

矩阵变幻 $2$ 次后：

输入一行一个不超过 $10$ 的正整数 $n$ 。输出变幻 $n$ 次后的矩阵。

试补全程序。

提示：

#include <cstdio>
using namespace std;
int n;
const int max_size = 1 << 10;

int res[max_size][max_size];

void recursive(int x, int y, int n, int t) {
    if (n == 0) {
        res[x][y] = ①;
        return;
    }
    int step = 1 << (n - 1);
    recursive(②, n - 1, t);
    recursive(x, y + step, n - 1, t);
    recursive(x + step, y, n - 1, t);
    recursive(③, n - 1, !t);
}

int main() {
    scanf("%d", &n);
    recursive(0, 0, ④);
    int size = ⑤;
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++)
            printf("%d", res[i][j]);
        puts("");
    }
    return 0;
}

程序

35（②）单选空位 ②3 分
②处应填（）

A
x-step,y-step

B
x,y-step

C
x-step,y

D
x,y

完善程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

1.（矩阵变幻）有一个奇幻的矩阵，在不停的变幻，其变幻方式为：

数字 $0$ 变成矩阵

0 0 
0 1

数字 $1$ 变成矩阵

1 1
1 0

最初该矩阵只有一个元素 $0$ ，变幻 $n$ 次后，矩阵会变成什么样？

例如，矩阵最初为： $[0]$ ；

矩阵变幻 $1$ 次后：

0 0 
0 1

矩阵变幻 $2$ 次后：

输入一行一个不超过 $10$ 的正整数 $n$ 。输出变幻 $n$ 次后的矩阵。

试补全程序。

提示：

#include <cstdio>
using namespace std;
int n;
const int max_size = 1 << 10;

int res[max_size][max_size];

void recursive(int x, int y, int n, int t) {
    if (n == 0) {
        res[x][y] = ①;
        return;
    }
    int step = 1 << (n - 1);
    recursive(②, n - 1, t);
    recursive(x, y + step, n - 1, t);
    recursive(x + step, y, n - 1, t);
    recursive(③, n - 1, !t);
}

int main() {
    scanf("%d", &n);
    recursive(0, 0, ④);
    int size = ⑤;
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++)
            printf("%d", res[i][j]);
        puts("");
    }
    return 0;
}

程序

36（③）单选空位 ③3 分
③处应填（）

A
x-step,y-step

B
x+step,y+step

C
x-step,y

D
x,y-step

完善程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

1.（矩阵变幻）有一个奇幻的矩阵，在不停的变幻，其变幻方式为：

数字 $0$ 变成矩阵

0 0 
0 1

数字 $1$ 变成矩阵

1 1
1 0

最初该矩阵只有一个元素 $0$ ，变幻 $n$ 次后，矩阵会变成什么样？

例如，矩阵最初为： $[0]$ ；

矩阵变幻 $1$ 次后：

0 0 
0 1

矩阵变幻 $2$ 次后：

输入一行一个不超过 $10$ 的正整数 $n$ 。输出变幻 $n$ 次后的矩阵。

试补全程序。

提示：

#include <cstdio>
using namespace std;
int n;
const int max_size = 1 << 10;

int res[max_size][max_size];

void recursive(int x, int y, int n, int t) {
    if (n == 0) {
        res[x][y] = ①;
        return;
    }
    int step = 1 << (n - 1);
    recursive(②, n - 1, t);
    recursive(x, y + step, n - 1, t);
    recursive(x + step, y, n - 1, t);
    recursive(③, n - 1, !t);
}

int main() {
    scanf("%d", &n);
    recursive(0, 0, ④);
    int size = ⑤;
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++)
            printf("%d", res[i][j]);
        puts("");
    }
    return 0;
}

程序

37（④）单选空位 ④3 分
④处应填（）

A
n-1,n%2

B
n,0

C
n,n%2

D
n-1,0

阅读程序共 1.5 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

原卷作答说明：判断题正确填 √，错误填 ×

程序

#include <algorithm>#include <iostream>using namespace std;int n;int d[50][2];int ans;void dfs(int n, int sum) { if (n == 1) { ans = max(sum, ans); return; } for (int i = 1; i < n; ++i) { int a = d[i - 1][0], b = d[i - 1][1]; int x = d[i][0], y = d[i][1]; d[i - 1][0] = a + x; d[i - 1][1] = b + y; for (int j = i; j < n - 1; ++j) d[j][0] = d[j + 1][0], d[j][1] = d[j + 1][1]; int s = a + x + abs(b - y); dfs(n - 1, sum + s); for (int j = n - 1; j > i; --j) d[j][0] = d[j - 1][0], d[j][1] = d[j - 1][1]; d[i - 1][0] = a, d[i - 1][1] = b; d[i][0] = x, d[i][1] = y; }}int main() { cin >> n; for (int i = 0; i < n; ++i) cin >> d[i][0]; for (int i = 0; i < n; ++i) cin >> d[i][1]; ans = 0; dfs(n, 0); cout << ans << endl; return 0;}

原文保真说明：来源改写 1 处（照原卷保留，未作修改）

来源题面被改写其它程序
原卷作 for (int i = 0; i < n; ++i) cin >> d[i][0]; ，常规写法应为 for (int i = 0; i < n; ++i) cin >> d[i][0];
洛谷抓取件 program.code 含行尾填充空格且 main 读入 d[i][1] 循环格式不同；pages/pg-06.png–pg-07.png 逐行核对后已恢复。
已按官方原件恢复：现为原卷原文

28判断1.5 分
若输入 $n$ 为 $0$ ，此程序可能会死循环或发生运行错误。（）

阅读程序共 1.5 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

原卷作答说明：判断题正确填 √，错误填 ×

程序

原文保真说明：来源改写 1 处（照原卷保留，未作修改）

来源题面被改写其它程序
原卷作 for (int i = 0; i < n; ++i) cin >> d[i][0]; ，常规写法应为 for (int i = 0; i < n; ++i) cin >> d[i][0];
洛谷抓取件 program.code 含行尾填充空格且 main 读入 d[i][1] 循环格式不同；pages/pg-06.png–pg-07.png 逐行核对后已恢复。
已按官方原件恢复：现为原卷原文

29判断1.5 分
若输入 $n$ 为 $20$ ，接下来的输入全为 $0$ ，则输出为 $0$ 。（）

考虑如下递归算法

solve(n)  
     if n<=1 return 1  
      else if n>=5 return n*solve(n-2)  
      else return n*solve(n-1)

则调用 solve(7) 得到的返回结果为（）。

105

840

210

420

以下对递归方法的描述中，正确的是：（）。

递归是允许使用多组参数调用函数的编程技术

递归是通过调用自身来求解问题的编程技术

递归是面向对象和数据而不是功能和逻辑的编程语言模型

递归是将用某种高级语言转换为机器代码的编程技术

阅读程序共 1.5 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

原卷作答说明：判断题正确填 √，错误填 ×

程序

#include <iostream>#include <cmath>using namespace std;int customFunction(int a, int b) { if (b == 0) { return a; } return a + customFunction(a, b-1);}int main() { int x, y; cin >> x >> y; int result = customFunction(x, y); cout << pow(result, 2) << endl; return 0;}

27判断1.5 分
当输入为 2 3 时，customFunction(2, 3) 的返回值为 $64$ 。（）

阅读程序共 1.5 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

原卷作答说明：判断题正确填 √，错误填 ×

程序

28判断1.5 分
当 $b$ 为负数时，customFunction(a, b) 会陷入无限递归。（）

阅读程序共 1.5 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

原卷作答说明：判断题正确填 √，错误填 ×

程序

29判断1.5 分
当 $b$ 的值越大，程序的运行时间越长。（）

阅读程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

程序

30单选3 分
单选题
1. 当输入为 5 4 时，customFunction(5, 4) 的返回值为（）。
A
5

B
25

C
250

D
625

阅读程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

程序

31单选3 分
如果输入 x=3 和 y=3，则程序的最终输出为（）。

A
27

B
81

C
144

D
256

阅读程序共 4 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

程序

32单选4 分
（4 分）若将 customFunction 函数改为 return a + customFunction(a-1, b-1);，并输入 3 3，则程序的最终输出为（）。

A
9

B
16

C
25

D
36

完善程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

（汉诺塔问题） 给定三根柱子，分别标记为 A、B 和 C。初始状态下，柱子 A 上有若干个圆盘，这些圆盘从上到下按从小到大的顺序排列。任务是将这些圆盘全部移到柱子 C 上，且必须保持原有顺序不变。在移动过程中，需要遵守以下规则:

只能从一根柱子的顶部取出圆盘，并将其放入另一根柱子的顶部。
每次只能移动一个圆盘。
小圆盘必须始终在大圆盘之上。

试补全程序。

#include <iostream>
#include <vector>
using namespace std;

void move(char src, char tgt) {
    cout << "从柱子" << src << "挪到柱子" << tgt << endl;
}

void dfs(int i, char src, char tmp, char tgt) {
    if (i == ___①___) {
        move(___②___);
        return;
    }
    dfs(i - 1, ___③___);
    move(src, tgt);
    dfs(___⑤___, ___④___);
}

int main() {
    int n;
    cin >> n;
    dfs(n, 'A', 'B', 'C');
}

程序

#include <iostream>#include <vector>using namespace std;void move(char src, char tgt) { cout << "从柱子" << src << "挪到柱子" << tgt << endl;}void dfs(int i, char src, char tmp, char tgt) { if (i == ___①___) { move(___②___); return; } dfs(i - 1, ___③___); move(src, tgt); dfs(___⑤___, ___④___);}int main() { int n; cin >> n; dfs(n, 'A', 'B', 'C');}

38（①）单选空位 ①3 分
① 处应填（）

A
0

B
1

C
2

D
3

完善程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

只能从一根柱子的顶部取出圆盘，并将其放入另一根柱子的顶部。
每次只能移动一个圆盘。
小圆盘必须始终在大圆盘之上。

试补全程序。

#include <iostream>
#include <vector>
using namespace std;

void move(char src, char tgt) {
    cout << "从柱子" << src << "挪到柱子" << tgt << endl;
}

void dfs(int i, char src, char tmp, char tgt) {
    if (i == ___①___) {
        move(___②___);
        return;
    }
    dfs(i - 1, ___③___);
    move(src, tgt);
    dfs(___⑤___, ___④___);
}

int main() {
    int n;
    cin >> n;
    dfs(n, 'A', 'B', 'C');
}

程序

40（③）单选空位 ③3 分
③ 处应填（）

A
src, tmp, tgt

B
src, tgt, tmp

C
tgt, tmp, src

D
tgt, src, tmp

完善程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

只能从一根柱子的顶部取出圆盘，并将其放入另一根柱子的顶部。
每次只能移动一个圆盘。
小圆盘必须始终在大圆盘之上。

试补全程序。

#include <iostream>
#include <vector>
using namespace std;

void move(char src, char tgt) {
    cout << "从柱子" << src << "挪到柱子" << tgt << endl;
}

void dfs(int i, char src, char tmp, char tgt) {
    if (i == ___①___) {
        move(___②___);
        return;
    }
    dfs(i - 1, ___③___);
    move(src, tgt);
    dfs(___⑤___, ___④___);
}

int main() {
    int n;
    cin >> n;
    dfs(n, 'A', 'B', 'C');
}

程序

41（④）单选空位 ④3 分
④ 处应填（）

A
src, tmp, tgt

B
tmp, src, tgt

C
src, tgt, tmp

D
tgt, src, tmp

完善程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

只能从一根柱子的顶部取出圆盘，并将其放入另一根柱子的顶部。
每次只能移动一个圆盘。
小圆盘必须始终在大圆盘之上。

试补全程序。

#include <iostream>
#include <vector>
using namespace std;

void move(char src, char tgt) {
    cout << "从柱子" << src << "挪到柱子" << tgt << endl;
}

void dfs(int i, char src, char tmp, char tgt) {
    if (i == ___①___) {
        move(___②___);
        return;
    }
    dfs(i - 1, ___③___);
    move(src, tgt);
    dfs(___⑤___, ___④___);
}

int main() {
    int n;
    cin >> n;
    dfs(n, 'A', 'B', 'C');
}

程序

42（⑤）单选空位 ⑤3 分
⑤ 处应填（）

A
0

B
1

C
i - 1

D
i

函数 calc(n) 的定义如下，则 calc(5) 的返回值是多少？（）

int calc(int n) {
    if (n <= 1) return 1;
    if (n % 2 == 0) return calc(n / 2) + 1;
    else return calc(n - 1) + calc(n - 2);
}

$5$

$6$

$7$

$8$

阅读程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

程序

#include <algorithm>#include <cstdio>#include <cstring>inline int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b);}int main() { int n; scanf("%d", &n); int ans = 0; for (int i = 1; i <= n; ++i) { for (int j = i + 1; j <= n; ++j) { for (int k = j + 1; k <= n; ++k) { if (gcd(i, j) == 1 && gcd(j, k) == 1 && gcd(i, k) == 1) { ++ans; } } } } printf("%d\n", ans); return 0;}

19单选3 分
将第 $7$ 行的 gcd(b, a%b) 改为 gcd(a, a%b) 后，程序可能出现的问题是（）。

A
输出的答案大于原答案。

B
输出的答案小于原答案。

C
程序有可能陷入死循环。

D
可能发生整型溢出问题。

递归函数

递归函数

单选题