#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(2n2^n)
  • 计算 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!)