题目导航

林老师 · 客观题题库 · 专题 13 递归与递推 · 复习强化

专题 13 递归与递推 · 复习强化

100 题 · 每题对应一个知识细节 · 全部原创

真题
复刻

试卷编号ORIG-专题13递归与递推-复习强化

题目总数103 题 · 100 分

试卷类型客观题

考生须知：
① 本卷共 10 大部分，合计 103 题 · 100 分，全部为客观题；
② 试卷右上角设有 「提交答卷」 与 「重置考试」 按钮，提交后系统自动判分并显示答题正确情况，请确认全部作答后再行提交；
③ 试卷不显示答案，提交后方可查看每题作答与正确答案的对照；
④ 答卷进度会保留在本地缓存中，刷新或再次打开仍可继续作答；
⑤ 本卷仅供学生练习使用；请勿用于其他用途；题面有问题请联系：i64coder@163.com。

判分报告

0 / 100 分

答对 · 得 0 分

答错 · 失 0 分

未作答

当前筛选下没有题目

壹

递归基础

14 QUESTIONS · 2 POINTS EACH

第 1 题 A1 未作答

递归是通过（）来求解问题的编程技术。（2022 年真题）

（1 分）

将高级语言转换为机器代码

使用多组参数调用函数

调用自身

面向对象和数据

第 2 题 A2 未作答

递归函数中终止条件（base case）的作用是（）。

（1 分）

加速程序

节省内存

停止递归调用、返回确定值——没有终止条件递归永不停止直至栈溢出

没有作用

第 3 题 A3 未作答

f(3) 调用 f(2) 调用 f(1)，f(1) 返回后执行顺序是（）。

（1 分）

f(2) 中调用 f(1) 之后的代码先执行，然后 f(2) 返回，f(3) 继续执行——后进先出

f(3) 先返回

不确定

同时返回

第 4 题 A4 未作答

递归函数在计算机内部通过（）管理调用。

（1 分）

队列

堆

栈——每层调用压入栈帧、返回时弹出

链表

第 5 题 A5 未作答

f(n) 调用 f(n-1) 直到 f(0)，递归深度是（）。

（1 分）

$n$

$0$

$1$

$n^2$

第 6 题 A6 未作答

01int f(int n) { return f(n + 1); }

调用 f(0) 的结果是（）。

（1 分）

栈溢出——递归无限加深

返回 $0$

返回 $\infty$

编译错误

第 7 题 A7 未作答

递归函数设计时每层调用的参数必须（）。

（1 分）

保持不变

增大

朝终止条件靠近——如 f(n) 调用 f(n-1)（ $n$ 减小趋向 $0$ ）

任意变化

第 8 题 A8 未作答

01int g(int n) {
02    if (n <= 0) return 0;
03    return g(n / 2) + n;
04}

g(7) 的返回值是（）。

（1 分）

$10$

$3$

$13$

$7$

第 9 题 A9 未作答

$n = 10^6$ 的递归求和应改用循环，主要原因是（）。

（1 分）

没有原因

循环更精确

递归不能处理大数

递归深度 $10^6$ 超过系统栈空间（约 $1\sim8$ MB），栈溢出

第 10 题 A10 未作答

尾递归是指（）。

（1 分）

只递归一层

递归调用是函数的最后一个操作——某些编译器可优化为循环

没有参数

最后一行是 return 0

第 11 题 A11 未作答

调试递归最有效的方法是（）。

（1 分）

删除递归

换编译器

在函数入口打印递归深度和参数值——追踪每层调用与返回

只看最终结果

第 12 题 A12 未作答

递归函数的标准代码结构是（）。

（1 分）

只有终止条件

终止条件判断（base case）→ 递归调用（缩小规模）→ 合并结果（return）

只有递归调用没有终止条件

不需要结构

第 13 题 A13 未作答

递归的优点是（）。

（1 分）

运行速度最快

永远不会出错

不消耗栈空间

代码简洁清晰、自然表达分治/树/图等递归结构

第 14 题 A14 未作答

关于递归，错误的是（）。

（1 分）

递归使用系统栈

递归可以转循环

必须有终止条件

所有递归都比循环快

贰

递归代码阅读

16 QUESTIONS · 2 POINTS EACH

第 15 题 B1 未作答

01int s(int n) { if (n == 0) return 0; return n + s(n - 1); }

s(4) 的返回值是（）。

（1 分）

$10$

$24$

$20$

$4$

第 16 题 B2 未作答

01int f(int n) { if (n <= 1) return 1; return n * f(n - 1); }

f(5) 的返回值是（）。

（1 分）

$5$

$720$

$120$

$25$

第 17 题 B3 未作答

递归算法 XYZ(A[1..n])：如果 $n=1$ 返回 $A[1]$ ；否则 temp ← XYZ(A[1..n-1])，如果 temp < A[n] 返回 temp 否则返回 A[n]。该算法输出的是（）。（2020 年真题）

（1 分）

$A$ 数组的最小值

$A$ 数组的最大值

$A$ 数组的平均

$A$ 数组的中值

第 18 题 B4 未作答

01int p(int a, int n) {
02    if (n == 0) return 1;
03    return a * p(a, n - 1);
04}

p(2, 3) 的返回值是（）。

（1 分）

$5$

$8$

$6$

$9$

第 19 题 B5 未作答

01solve(n)
02  if n<=1 return 1
03  else if n>=5 return n*solve(n-2)
04  else return n*solve(n-1)

solve(7) 的返回值是（）。（2021 年真题）

（1 分）

$210$

$420$

$840$

$105$

第 20 题 B6 未作答

01void p(int n) {
02    if (n == 0) { cout << "*"; return; }
03    p(n - 1);
04    cout << n;
05}

p(3) 输出（）。

（1 分）

*321

123*

*123

321*

第 21 题 B7 未作答

01int q(int a, int b) {
02    if (b == 0) return a;
03    return q(b, a % b);
04}

q(12, 8) 的返回值是（）。

（1 分）

$8$

$0$

$12$

$4$

第 22 题 B8 未作答

01int c(int n) {
02    if (n <= 1) return 1;
03    return c(n - 1) + c(n - 2);
04}

c(5) 的返回值是（）。

（1 分）

$13$

$8$

$6$

$5$

第 23 题 B9 未作答

01int s(int arr[], int n) {
02    if (n == 0) return 0;
03    return arr[n-1] + s(arr, n-1);
04}

int a[] = {1, 2, 3}; s(a, 3) 返回（）。

（1 分）

$3$

$1$

$6$

$0$

第 24 题 B10 未作答

01void rev(string& s, int l, int r) {
02    if (l >= r) return;
03    swap(s[l], s[r]);
04    rev(s, l + 1, r - 1);
05}

rev("abc", 0, 2) 后字符串变为（）。

（1 分）

bac

abc

acb

cba

第 25 题 B11 未作答

01int bs(int a[], int l, int r, int x) {
02    if (l > r) return -1;
03    int mid = (l + r) / 2;
04    if (a[mid] == x) return mid;
05    if (a[mid] > x) return bs(a, l, mid - 1, x);
06    return bs(a, mid + 1, r, x);
07}

此算法的递归深度（最坏情况）是（）。

（1 分）

$O(1)$

$O(\log n)$ ——每次范围减半

$O(n)$

$O(n \log n)$

第 26 题 B12 未作答

01int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

gcd(48, 36) 递归调用了（）次。

（1 分）

$1$

$3$

$4$

$2$

第 27 题 B13 未作答

01int fib(int n) {
02    if (n <= 1) return n;
03    return fib(n-1) + fib(n-2);
04}

fib(5) 的总调用次数（含 fib(0) 和 fib(5) 自身）是（）。

（1 分）

$8$

$15$

$6$

$5$

第 28 题 B14 未作答

01void hanoi(int n, char a, char b, char c) {
02    if (n == 0) return;
03    hanoi(n-1, a, c, b);
04    cout << a << "->" << c << " ";
05    hanoi(n-1, b, a, c);
06}

hanoi(2, 'A', 'B', 'C') 输出（）。

（1 分）

A->C A->B B->C

A->C A->C

A->C B->A B->C A->C

A->B A->C B->C

第 29 题 B15 未作答

01int f(int n) {
02    if (n > 2) { f(n / 2); cout << n << " "; }
03    else cout << n << " ";
04}

f(12) 输出（）。

（1 分）

3

12 6 3

12

3 6 12

第 30 题 B16 未作答

01int m(int a, int b) {
02    if (b == 1) return a;
03    return a + m(a, b - 1);
04}

m(3, 4) 的返回值是（）。

（1 分）

$12$

$7$

$9$

$81$

叁

递归与分治

10 QUESTIONS · 2 POINTS EACH

第 31 题 C1 未作答

分治法的三个步骤是（）。

（1 分）

读→算→写

分（拆子问题）→ 治（递归解决）→ 合（合并结果）

输入→处理→输出

比较→交换→移动

第 32 题 C2 未作答

分治与递归的关系是（）。

（1 分）

递归是分治的一种

完全等价

分治不能用递归

分治通常用递归实现——"分"就是递归调用自身；但递归不一定是分治（单路递归没有"分"）

第 33 题 C3 未作答

分析递归复杂度的"递归树"方法核心是（）。

（1 分）

只看最深层

数节点

逐层展开递归、计算每层总代价、所有层求和

只看叶子

第 34 题 C4 未作答

f(n) 调用 f(n-1)（单分支、每层 $O(1)$ ）的时间复杂度是（）。

（1 分）

$O(1)$

$O(n)$

$O(2^n)$

$O(\log n)$

第 35 题 C5 未作答

f(n) 调用 f(n/2)（单分支、每层 $O(1)$ ）的时间复杂度是（）。

（1 分）

$O(n/2)$

$O(2^n)$

$O(n)$

$O(\log n)$

第 36 题 C6 未作答

fib(n) 调用 fib(n-1) 和 fib(n-2)（双子树）的时间复杂度约是（）。

（1 分）

$O(n \log n)$

$O(2^n)$

$O(n)$

$O(n^2)$

第 37 题 C7 未作答

归并排序的递归式是（）。

（1 分）

$T(n) = 2T(n-1) + O(1)$ ，解 $O(2^n)$

$T(n) = T(n/2) + O(1)$ ，解 $O(\log n)$

$T(n) = T(n-1) + O(1)$ ，解 $O(n)$

$T(n) = 2T(n/2) + O(n)$ ，解 $O(n \log n)$

第 38 题 C8 未作答

快速排序最坏情况的递归式是（）。

（1 分）

$T(n) = 2T(n/2) + O(n)$

$O(n)$

$T(n) = T(n/2) + O(1)$

$T(n) = T(n-1) + O(n)$ ，解 $O(n^2)$ ——分区极不平衡

第 39 题 C9 未作答

分治适用条件不包括（）。

（1 分）

子问题之间必须有交集

子问题解可合并

问题可分解为同类子问题

子问题独立

第 40 题 C10 未作答

关于分治，错误的是（）。

（1 分）

二分查找可看作分治特例

归并排序是分治

所有问题都能用分治高效解决

分治复杂度可用主定理

肆

递推基础

14 QUESTIONS · 2 POINTS EACH

第 41 题 D1 未作答

递推的定义是（）。

（1 分）

从大往小算

随机生成数列

每一项由前面的项通过确定的公式计算——自底向上填表

只适用于斐波那契

第 42 题 D2 未作答

递推与递归的关系是（）。

（1 分）

递推自底向上（从小到大填表）；递归自顶向下（从大拆到小）——本质等价

完全无关

只能选一种

递推比递归慢

第 43 题 D3 未作答

递推 $f(n) = f(n-1) + 3$ ， $f(1) = 1$ 。 $f(5) = ?$ （）。

（1 分）

$13$

$15$

$16$

$10$

第 44 题 D4 未作答

递推 $f(1)=1, f(2)=1$ ， $f(n) = f(n-1) + f(n-2)$ 。 $f(7) = ?$ （）。

（1 分）

$8$

$11$

$21$

$13$

第 45 题 D5 未作答

递推 $f(n) = f(n-1) + f(n-2)$ ， $f(1)=1, f(2)=1$ 得斐波那契；改为 $f(1)=1, f(2)=3$ 得（）。

（1 分）

常数列

Lucas 数列——递推相同但初始值不同产生不同数列

仍是斐波那契

等差数列

第 46 题 D6 未作答

递推编程的标准框架是（）。

（1 分）

不需要初始值

从 $n$ 往回推

初始化 $f[1], f[2]$ → for (i = 3; i <= n; ++i) f[i] = ... → 输出 $f[n]$

递归函数调用自身

第 47 题 D7 未作答

递推 $f[0]=0, f[1]=1$ ， $f[i] = f[i-1] + f[i-2]$ 。 $f[6] = ?$ （）。

（1 分）

$5$

$8$

$13$

$21$

第 48 题 D8 未作答

递推 $f(n) = 2f(n-1)$ （ $f(1)=1$ ）的通项公式是（）。

（1 分）

$f(n) = 2^{n-1}$

$f(n) = 2n$

$f(n) = n$

$f(n) = n^2$

第 49 题 D9 未作答

斐波那契 $f(50) \approx 1.2 \times 10^{10}$ 。int（上限约 $2.1 \times 10^9$ ）（）存下。

（1 分）

不能——应用 long long

取决于编译器

能

用 float 可以

第 50 题 D10 未作答

递推 $f(n) = f(n-1) + f(n-2)$ 只需前两项，不开数组只保留两个变量的做法叫（）。

（1 分）

不可能

记忆化

滚动变量——空间从 $O(n)$ 降到 $O(1)$

打表

第 51 题 D11 未作答

递推与动态规划的关系是（）。

（1 分）

DP 不能用递推

无关

线性递推是最简单的 DP——状态转移方程就是 DP 的转移方程

递推比 DP 慢

第 52 题 D12 未作答

递推 $f[i] = f[i-1] + f[i-2]$ 从 $i = ?$ 开始循环（ $f[0]$ 、 $f[1]$ 已初始化）（）。

（1 分）

$i = 2$

$i = 0$

$i = 1$

$i = 3$

第 53 题 D13 未作答

递推 $f(n) = 3 \cdot f(n-1)$ （ $f(0)=1$ ）， $f(4) = ?$ （）。

（1 分）

$64$

$81$

$12$

$27$

第 54 题 D14 未作答

关于递推，错误的是（）。

（1 分）

可以空间优化

需要正确初始条件

递推就是递归的另一种叫法

递推自底向上

伍

斐波那契与变式

12 QUESTIONS · 2 POINTS EACH

第 55 题 E1 未作答

斐波那契数列的定义是（）。

（1 分）

$f(1) = f(2) = 1$ ， $f(n) = f(n-1) + f(n-2)$

$f(n) = 2^n$

$f(n) = n^2$

$f(n) = n!$

第 56 题 E2 未作答

斐波那契 $f(1)=1, f(2)=1$ 。 $f(8) = ?$ （）。

（1 分）

$18$

$34$

$13$

$21$

第 57 题 E3 未作答

递推 $f(1)=1, f(2)=2$ ， $f(n) = f(n-1) + f(n-2)$ 。 $f(6) = ?$ （）。

（1 分）

$8$

$16$

$21$

$13$

第 58 题 E4 未作答

递推 $f(1)=2, f(2)=1$ ， $f(n) = f(n-1) + f(n-2)$ 。 $f(5) = ?$ （）。

（1 分）

$7$

$12$

$8$

$5$

第 59 题 E5 未作答

每次上 $1$ 或 $2$ 阶台阶，上 $n$ 阶的方法数 $f(n) = ?$ （）。

（1 分）

$f(n) = 2^n$

$f(n) = n^2$

$f(n) = f(n-1) + f(n-2)$ ——最后一步上 $1$ 阶或 $2$ 阶

$f(n) = n$

第 60 题 E6 未作答

每次上 $1$ 、 $2$ 或 $3$ 阶台阶，上 $n$ 阶的方法数递推是（）。

（1 分）

$f(n) = f(n-1) + f(n-2)$

$f(n) = 3 \cdot f(n-1)$

$f(n) = n^3$

$f(n) = f(n-1) + f(n-2) + f(n-3)$

第 61 题 E7 未作答

long long 可存到 $20!$ 。斐波那契第（）项开始超 long long。

（1 分）

$93$ （ $f(92) \approx 7.5 \times 10^{18}$ 未超， $f(93)$ 超）

$50$

$200$

$100$

第 62 题 E8 未作答

朴素斐波那契递归 fib(40) 在普通电脑上（）。

（1 分）

需要 $40$ GB 内存

只能用迭代

需数秒到数十秒—— $O(2^n)$ 指数爆炸

瞬间完成

第 63 题 E9 未作答

斐波那契从递归 $O(2^n)$ 优化到迭代 $O(n)$ 的关键是（）。

（1 分）

减少了内存

每个值只算一次——自底向上填表，避免重复计算

用了更快 CPU

用公式直接算

第 64 题 E10 未作答

Lucas 数列 $L(1)=1, L(2)=3$ ， $L(n) = L(n-1) + L(n-2)$ 。 $L(5) = ?$ （）。

（1 分）

$5$

$11$

$13$

$8$

第 65 题 E11 未作答

斐波那契数列相邻两项的比值 $\frac{f(n+1)}{f(n)}$ 趋近于（）。

（1 分）

$1$

$2$

$\pi$

黄金比 $\phi = \frac{1+\sqrt{5}}{2} \approx 1.618$

第 66 题 E12 未作答

关于斐波那契数列，错误的是（）。

（1 分）

朴素递归 $O(2^n)$

$f(n)$ 一定是素数

迭代可 $O(n)$

递推 $f(n) = f(n-1) + f(n-2)$

陆

汉诺塔

10 QUESTIONS · 2 POINTS EACH

第 67 题 F1 未作答

汉诺塔问题： $n$ 个盘子从 A 移到 C（借助 B），每次移一个、大盘不能在小盘上面。至少需要（）次移动。

（1 分）

$2^n - 1$

$n!$

$n$

$n^2$

第 68 题 F2 未作答

汉诺塔递推 $h(n) = 2h(n-1) + 1$ ， $h(1) = 1$ 。 $h(5) = ?$ （）。

（1 分）

$15$

$32$

$16$

$31$

第 69 题 F3 未作答

汉诺塔递归的正确代码结构是（）。

（1 分）

hanoi(n-1, a, c, b); 移动第 $n$ 盘 a->c; hanoi(n-1, b, a, c);

hanoi(n, a, b, c);（不减小 $n$ ）

只移一次

不需要递归

第 70 题 F4 未作答

汉诺塔 $n=2$ （A→C 借助 B），移动序列是（）。

（1 分）

A→C, A→C

A→B, A→C, B→C

A→B, A→C

A→C, A→B, B→C

第 71 题 F5 未作答

汉诺塔 $n = 3$ 至少需要（）次移动。

（1 分）

$7$

$8$

$5$

$6$

第 72 题 F6 未作答

汉诺塔递归 hanoi(n, src, tmp, tgt) 中第二参数和第三参数的含义是（）。

（1 分）

两个临时柱

源和目标

目标和源

源和临时柱（目标在第四参数）——三个柱子角色在递归中互换

第 73 题 F7 未作答

汉诺塔的时间复杂度是（）。

（1 分）

$O(n^2)$

$O(n)$

$O(n \log n)$

$O(2^n)$ ——移动次数 $2^n - 1$

第 74 题 F8 未作答

汉诺塔递归的正确性来自：把 $n$ 盘问题分解为（）。

（1 分）

先把 $n-1$ 个盘从 A 移到 B（借助 C），再把最大盘 A→C，最后把 $n-1$ 盘从 B 移到 C（借助 A）

不需要分解

直接把所有盘一起移

每次随机移一个

第 75 题 F9 未作答

汉诺塔在竞赛中的典型意义是（）。

（1 分）

字符串匹配

排序

递归思想的经典教学案例——展示分治与递归的威力

最短路

第 76 题 F10 未作答

关于汉诺塔，错误的是（）。

（1 分）

$n=64$ 时移动次数约 $1.8 \times 10^{19}$

汉诺塔可以用 $O(n)$ 时间解决

递归实现最自然

$h(n) = 2^n - 1$

柒

递归与递推互转

10 QUESTIONS · 2 POINTS EACH

第 77 题 G1 未作答

递归 $f(n) = f(n-1) + n$ （ $f(0)=0$ ）改写为循环是（）。

（1 分）

无法转循环

改写后更复杂

int s = 0; for (int i = 1; i <= n; ++i) s += i;

只能用递归

第 78 题 G2 未作答

递推 $f[i] = f[i-1] + f[i-2]$ 改写为递归是（）。

（1 分）

int f(int n) { if (n <= 1) return n; return f(n-1) + f(n-2); }

不需要改

不能转

转了更慢所以不转

第 79 题 G3 未作答

递归相对递推的优缺点是（）。

（1 分）

两者完全相同

只有优点

只有缺点

优点：代码简洁自然；缺点：消耗栈空间、可能溢出、可能有重复计算

第 80 题 G4 未作答

选择递归还是递推的主要依据是（）。

（1 分）

个人喜好

递归深度是否安全（ $> 10^5$ 用递推）以及是否存在重复子问题（有用则加记忆化或用递推）

代码越短越好

总是选递归

第 81 题 G5 未作答

递归深度 $10^6$ 的函数要避免栈溢出，正确做法是（）。

（1 分）

改为循环或用显式栈模拟递归

没有办法

用浮点数

增加内存

第 82 题 G6 未作答

用递推表填充替代递归的好处是（）。

（1 分）

代码更短

不需要初始条件

避免栈溢出和避免重复计算——每个值只算一次

更精确

第 83 题 G7 未作答

记忆化递归的核心是（）。

（1 分）

用多线程

用数组缓存已算过的子问题结果——再次遇到直接查表

改用循环

随机化

第 84 题 G8 未作答

斐波那契从递归转递推后时间复杂度从 $O(2^n)$ 变为（）。

（1 分）

$O(1)$

$O(n \log n)$

$O(\log n)$

$O(n)$

第 85 题 G9 未作答

递推 $f[i] = f[i-1] \times 2$ （ $f[0]=1$ ）转递归的正确写法是（）。

（1 分）

不需要转

int f(int n) { return 1; }

int f(int n) { if (n == 0) return 1; return 2 * f(n - 1); }

不能转

第 86 题 G10 未作答

关于递归与递推互转，错误的是（）。

（1 分）

互转后结果相同

所有递推都可以转递归

所有递归都可以转循环

互转后复杂度一定相同

捌

倍增法

6 QUESTIONS · 2 POINTS EACH

第 87 题 H1 未作答

倍增法的核心思想是（）。

（1 分）

只跳一次

随机跳跃

每次跳一步

预处理 $2^j$ 步的跳转结果——查询时用二进制分解组合跳到目标

第 88 题 H2 未作答

快速幂 $a^n \bmod m$ 用倍增思想，复杂度是（）。

（1 分）

$O(\log n)$ ——每次平方使指数减半

$O(1)$

$O(\sqrt{n})$

$O(n)$

第 89 题 H3 未作答

倍增求 LCA 时 fa[j][u] 的含义是（）。

（1 分）

$u$ 的深度

$u$ 的父结点

$u$ 向上跳 $2^j$ 步到达的祖先

$u$ 的第 $j$ 个孩子

第 90 题 H4 未作答

倍增法预处理 $n$ 个结点、 $\log n$ 层跳转表的空间复杂度是（）。

（1 分）

$O(n^2)$

$O(n \log n)$

$O(\log n)$

$O(n)$

第 91 题 H5 未作答

倍增预处理代码的核心递推是（）。

（1 分）

fa[j][u] = u

fa[j][u] = fa[j-1][fa[j-1][u]]——跳 $2^j$ 步等于先跳 $2^{j-1}$ 再跳 $2^{j-1}$

fa[j][u] = fa[j-1][u] + 1

不需要预处理

第 92 题 H6 未作答

关于倍增法，错误的是（）。

（1 分）

预处理 $O(n \log n)$

用于 LCA 和快速幂

查询 $O(\log n)$

倍增只能处理树上的问题

玖

综合与易错

8 QUESTIONS · 2 POINTS EACH

第 93 题 I1 未作答

递归函数的终止条件（）。

（1 分）

只能是 $n == 0$

必须有且参数必须朝其靠近

只能在函数开头

可以没有

第 94 题 I2 未作答

递推与递归的主要区别是（）。

（1 分）

递推更快

没有区别

递归更安全

递推自底向上、递归自顶向下

第 95 题 I3 未作答

斐波那契递归 fib(30) 慢的原因是（）。

（1 分）

大量重复计算——同一个子问题被计算多次

CPU 太慢

内存不够

递归太深

第 96 题 I4 未作答

汉诺塔 $h(n) = 2^n - 1$ ， $h(10) = ?$ （）。

（1 分）

$2047$

$1024$

$1023$

$512$

第 97 题 I5 未作答

关于倍增，正确的是（）。

（1 分）

fa[j][u] = fa[j-1][u] * 2

fa[j][u] = fa[j-1][fa[j-1][u]]

倍增不需要预处理

倍增只能用于排序

第 98 题 I6 未作答

递归深度 $10^5$ 的函数可能发生（）。

（1 分）

数组越界

没有问题

栈溢出——系统栈空间不够

编译错误

第 99 题 I7 未作答

递推 $f(n) = f(n-1) \times 2$ （ $f(0) = 1$ ）， $f(10) = ?$ （）。

（1 分）

$512$

$20$

$1024$

$100$

第 100 题 I8 未作答

关于递归与递推，错误的是（）。

（1 分）

两者可以互转

所有递归都比循环慢

递归使用系统栈

递推自底向上填表

拾

真题演练

3 QUESTIONS · 真题演练不计分

第 1 题单选未作答

设 $A$ 是 $n$ 个实数的数组，考虑下面的递归算法：

XYZ(A[1..n])
1 if n = 1 then return A[1]
2 else temp ← XYZ(A[1..n-1])
3      if temp < A[n]
4          then return temp
5          else return A[n]

请问算法 XYZ 的输出是什么？（）

（0 分）

$A$ 数组的平均

$A$ 数组的最小值

$A$ 数组的中值

$A$ 数组的最大值

CSP-J 2020 · 单选第6题｜知识点程序阅读与输出推断、递归、一维数组

第 2 题单选未作答

考虑如下递归算法

01solve(n)
02    if n<=1 return 1
03    else if n>=5 return n*solve(n-2)
04    else return n*solve(n-1)

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

（0 分）

$105$

$840$

$210$

$420$

CSP-J 2021 · 单选第13题｜知识点程序阅读与输出推断、递归函数、递归

第 3 题单选未作答

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

（0 分）

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

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

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

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

CSP-J 2022 · 单选第15题｜知识点递归函数、递归

重置作答

专题 13 递归与递推 · 复习强化

判 分 报 告

递归基础

递归代码阅读

递归与分治

递推基础

斐波那契与变式

汉诺塔

递归与递推互转

倍增法

综合与易错

真 题 演 练

打印

导出 HTML 子卷

判分报告

真题演练