递归与迭代（共 15 题）

单选题

1. 关于递归函数调用，下列说法错误的是（ ）。
   {{ select(1) }}

• 递归调用层次过深时，可能会耗尽栈空间导致栈溢出
• 尾递归函数可以通过编译器优化来避免栈溢出
• 所有递归函数都可以通过循环结构来改写，从而避免栈溢出
• 栈溢出发生时，程序会抛出异常并可以继续执行后续代码

2. 下面 C++ 代码用于求斐波那契数列，该数列第 1、2 项为 1，以后各项均是前两项之和。下面有关说法错误的是（ ）。

   int fiboA(int N) {
       if (N == 1 || N == 2) return 1;
       return fiboA(N-1) + fiboA(N-2);
   }
   int fiboB(int N) {
       if (N == 1 || N == 2) return 1;
       int last2 = 1, last1 = 1, nowVal = 0;
       for (int i = 2; i < N; i++) {
           nowVal = last1 + last2;
           last2 = last1;
           last1 = nowVal;
       }
       return nowVal;
   }
   

   {{ select(2) }}

• fiboA() 用递归方式，fiboB() 循环方式
• fiboA() 更加符合斐波那契数列的数学定义，直观易于理解，而 fiboB() 需要将数学定义转换为计算机程序实现
• fiboA() 不仅仅更加符合数学定义，直观易于理解，且因代码量较少执行效率更高
• fiboB() 虽然代码量有所增加，但其执行效率更高

3. 下面的 C++ 代码片段用于计算阶乘。请在横线处填入（ ），实现正确的阶乘计算。

   int factorial(int n) {
       if (n == 0 || n == 1) { return 1; }
       else { __________________ }
   }
   

   {{ select(3) }}

• return n * factorial(n-1);
• return factorial(n-1) / n;
• return n * factorial(n);
• return factorial(n/2) * factorial(n/2);

4. 递归函数在调用自身时，必须满足（ ），以避免无限递归。
   {{ select(4) }}

• 有终止条件
• 函数参数递减（或递增）
• 函数返回值固定
• 以上都对

5. 给定如下函数：

   int fun(int n) {
       if (n == 1) return 1;
       if (n == 2) return 2;
       return fun(n-2) - fun(n-1);
   }
   

   则当 n = 7 时，函数返回值为（ ）。
   {{ select(5) }}

• 0
• 1
• 21
• -11

6. 给定如下函数（函数功能同上题，增加输出打印）：

   int fun(int n) {
       cout << n << " ";
       if (n == 1) return 1;
       if (n == 2) return 2;
       return fun(n-2) - fun(n-1);
   }
   

   则当 n = 4 时，屏幕上输出序列为（ ）。
   {{ select(6) }}

• 4321
• 1234
• 42312
• 42321

7. 下面给出了阶乘计算的两种方式。以下说法正确的是（ ）。

   int factorial1(int n) {
       if (n <= 1) return 1;
       return n * factorial1(n-1);
   }
   int factorial2(int n) {
       int acc = 1;
       while (n > 1) {
           acc = n * acc;
           n = n - 1;
       }
       return acc;
   }
   

   {{ select(7) }}

• 上面两种实现方式的时间复杂度相同，都为 O(n)
• 上面两种实现方式的空间复杂度相同，都为 O(n)
• 上面两种实现方式的空间复杂度相同，都为 O(1)
• 函数 factorial1() 的时间复杂度为 O(2^n)，函数 factorial2() 的时间复杂度为 O(n)

8. 当 n = 7 时，下面函数的返回值为（ ）。

   int fun(int n) {
       if (n == 1) return 1;
       else if (n >= 5) return n * fun(n-2);
       else return n * fun(n-1);
   }
   

   {{ select(8) }}

• 105
• 840
• 210
• 420

9. 对下面两个函数，说法错误的是（ ）。

   int factorialA(int n) {
       if (n <= 1) return 1;
       return n * factorialA(n-1);
   }
   int factorialB(int n) {
       if (n <= 1) return 1;
       int res = 1;
       for(int i=2; i<=n; i++) res *= i;
       return res;
   }
   

   {{ select(9) }}

• 两个函数的实现的功能相同。
• 两个函数的时间复杂度均为 O(n)。
• factorialA 采用递归方式。
• factorialB 采用递归方式。

10. 下面代码用于求斐波那契数列，该数列第 1、2 项为 1，以后各项均是前两项之和。函数 fibo() 属于（ ）。

    int fibo(int n) {
        if (n <= 0) return 0;
        if (n == 1 || n == 2) return 1;
        int a = 1, b = 1, next;
        for (int i = 3; i <= n; i++) {
            next = a + b;
            a = b;
            b = next;
        }
        return next;
    }
    

    {{ select(10) }}

• 枚举算法
• 贪心算法
• 迭代算法
• 递归算法

判断题

11. 任何递归程序都可以改写为等价的非递归程序，但改写后的非递归程序一定需要显式地使用栈来模拟递归调用过程。
    {{ select(11) }}

• 正确
• 错误

12. 递归函数每次调用自身时，系统都会为新开启的函数分配内存，以存储局部变量、调用地址和其他信息等，导致递归通常比迭代更加耗费内存空间。
    {{ select(12) }}

• 正确
• 错误

13. 递归算法必须有一个明确的结束条件，否则会导致无限递归并可能引发栈溢出。
    {{ select(13) }}

• 正确
• 错误

14. 递归函数必须具有一个终止条件，以防止无限递归。
    {{ select(14) }}

• 正确
• 错误

15. 在 C++ 语言中，递归的实现方式通常会占用更多的栈空间，可能导致栈溢出。
    {{ select(15) }}

• 正确
• 错误