#cspjc13. 递归2
递归2
递归2
1.(递归边界与终止条件)阅读以下递归函数:
int func(int n) {
if (n == 0) return 0;
return n + func(n - 1);
}
关于该函数,下列说法正确的有( )?
{{ multiselect(1) }}
- 调用 func(5) 的返回值为 15
- 调用 func(-1) 会导致栈溢出(无限递归)
- 将边界条件改为 if (n <= 0) return 0; 可以增强函数的健壮性
- 该函数的空间复杂度为 O(1)
2.(递归深度与系统栈)已知某递归函数的时间复杂度为 O(n),空间复杂度为 O(n)。当 n = 100000 时,以下说法正确的有( )?{{ multiselect(2) }}
- 程序可能会因栈溢出(Stack Overflow)而崩溃
- 该递归函数一定存在大量的重复子问题计算
- 若该函数是尾递归形式,编译器可能将其优化为循环,从而降低空间复杂度
- 该递归函数的调用栈最大深度为 O(n)
3.(多路递归调用与复杂度)已知斐波那契数列的递归实现如下:
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
以下关于该递归算法的描述,正确的有( )?
{{ multiselect(3) }}
- 计算 fib(n) 时,函数调用的总次数约为 O()
- 计算 fib(5) 和 fib(4) 之间存在大量的重复计算
- 该递归算法的空间复杂度为 O(n)(不考虑系统栈则为O(1),但通常考虑栈)
- 若将边界条件改为 if (n == 1) return 1;,程序对于 fib(0) 依然能正确返回 0
4.(循环结构与递归调用的结合)阅读以下代码:
void solve(int n) {
if (n == 0) return;
for (int i = 1; i <= n; i++) {
cout << i;
}
solve(n - 1);
}
假设调用 solve(3),以下说法正确的有( )? {{ multiselect(4) }}
- 控制台输出结果为 12312
- 该算法的时间复杂度为 O(n²)
- 若将 for 循环放在 solve(n - 1); 之后,则输出结果会变为 112123
- 该递归函数的空间复杂度为 O(n)
5.(静态局部变量在递归中的特性)阅读以下代码:
void count_func(int n) {
static int cnt = 0;
cnt++;
if (n == 0) return;
count_func(n - 1);
cout << cnt;
}
调用 count_func(3); 后,以下说法正确的有( )?
{{ multiselect(5) }}
- 程序最终输出 444
- 静态变量 cnt 在递归过程中只被初始化一次
- 若将 static 关键字去掉,程序的输出结果将发生改变
- 函数执行结束后,cnt 的值为 3
6.(引用传参与递归累加 / 尾递归判定)阅读以下代码:
void accumulate(int n, int &sum) {
if (n == 0) return;
sum += n;
accumulate(n - 1, sum);
}
以下关于该函数的描述,正确的有( )?
{{ multiselect(6) }}
- 每次递归调用都会创建 sum 的一个新的副本
- 该递归属于尾递归(Tail Recursion)形式
- 若将函数参数 int &sum 改为 int sum,函数的最终计算结果不会改变
- 调用 accumulate(5, ans); 后,ans 的值为 15
7.(递归的“递推”与“回归”阶段顺序)阅读以下代码:
void print_seq(int n) {
if (n == 0) return;
cout << "A";
print_seq(n - 1);
cout << "B";
}
调用 print_seq(3);,以下说法正确的有( )?
{{ multiselect(7) }}
- 输出字符串的长度为 6
- 输出结果为 AAABBB
- 如果交换两条 cout 语句的顺序,输出结果会变为 BBBAAA
- 该递归过程中,所有 A 均是在“递推”阶段输出,所有 B 均是在“回归”阶段输出
8.(尾递归的概念与优化)关于尾递归,以下说法正确的有( )?{{ multiselect(8) }}
- 尾递归是指递归调用是函数体内最后一条可执行语句
- 任何尾递归算法都可以比较容易地改写成迭代(循环)算法
- C++ 标准规定所有编译器必须对尾递归进行强制优化
- 尾递归优化可以显著降低算法的空间复杂度,防止栈溢出
9.(复杂多分支递归与逻辑推理)阅读以下函数:
int f(int n) {
if (n <= 1) return 1;
if (n % 2 == 0) return f(n / 2) + 1;
else return f(n - 1) + f(n - 2);
}
以下关于该函数的描述,正确的有( )?{{ multiselect(9) }}
- 调用 f(5) 时,会先计算 f(4),再计算 f(3)
- 该递归过程中存在重叠子问题(重复计算)
- 该函数对于所有正整数入参最终都会终止(不会无限递归)
- 该递归算法的空间复杂度一定为 O(log n)
10.(递归实现全排列/回溯算法)阅读以下用于生成全排列的核心递归代码(arr为待排列数组):
void dfs(int pos, int n, int arr[]) {
if (pos == n) {
// 输出排列
return;
}
for (int i = pos; i < n; i++) {
swap(arr[pos], arr[i]);
dfs(pos + 1, n, arr);
swap(arr[pos], arr[i]); // 回溯
}
}
以下关于该算法的说法,正确的有( )?{{ multiselect(10) }}
- 该递归的深度为 n
- 递归树的叶子节点数量为 n!
- 最后的 swap 回溯操作是必需的,目的是恢复数组状态以便进行下一轮循环
- 该算法的时间复杂度为 O(n * n!)