七、递归与递推（共15题）

题目

1. 用递归法求n的阶乘，时间复杂度是O(n)。（判断题）
{{ select(1) }}

• 正确
• 错误

2. 下面代码采用递推算法实现整数n的阶乘，横线上应填写（ ）。

int factorial(int n) {
    int result=1;
    for(int i=2;i<=n;i++){
        ________;
    }
    return result;
}

{{ select(2) }}

• result*=i
• result+=i
• result*=result
• result+=result

3. 下面代码采用递推算法计算斐波那契数列，横线上应填写（ ）。

int fib(int n) {
    if(n==0||n==1) return n;
    int f1=0,f2=1,result=0;
    for(int i=2;i<=n;i++){
        ________;
    }
    return result;
}

{{ select(3) }}

• result=f1+f2; f1=f2; f2=result;
• result=f1+f2; f2=result; f1=f2;
• result=f1+f2; f1=result; f2=f1;
• f1=f2; f2=f1+f2; result=f2;

4. 给定如下递归函数，其时间复杂度为（ ）。

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

{{ select(4) }}

• O(n^2)
• O(2^n)
• O(1)
• O(n)

5. 小杨爬楼梯，每次1或2阶，下面递推算法横线处应填写（ ）。

int climbStairs(int n) {
    if(n<=2) return n;
    int f1=1,f2=2,res=0;
    for(int i=3;i<=n;i++){
        ________;
    }
    return res;
}

{{ select(5) }}

• res=f1+f2; f1=f2; f2=res;
• res+=f1+f2; f1=f2; f2=res;
• res=f1+f2; f2=res; f1=f2;
• res+=f1+f2; f2=res; f1=f2;

6. 给定函数，climbStairs(5)的返回值是（ ）。

int climbStairs(int n) {
    if(n<=2) return n;
    int a=1,b=2;
    for(int i=3;i<=n;i++){
        int temp=a+b;
        a=b;
        b=temp;
    }
    return b;
}

{{ select(6) }}

• 5
• 8
• 13
• 10

7. 下面递推方式计算斐波那契数列的时间复杂度是O(n)。（判断题）

int f[20];
f[0]=0; f[1]=1;
for(int i=2;i<=n;i++) f[i]=f[i-1]+f[i-2];

{{ select(7) }}

• 正确
• 错误

8. 下面程序计算阶乘，结果正确吗？（判断题）

int factorial(int n) {
    int res=1;
    for(int i=0;i<n;++i) res=i;
    return res;
}

{{ select(8) }}

• 正确
• 错误

9. 递推算法通过逐步求解当前状态和前一个或几个状态之间的关系来解决问题。（判断题）
{{ select(9) }}

• 正确
• 错误

10. 下列哪个问题适合用递推而非递归？（ ）
{{ select(10) }}

• 求斐波那契数列
• 汉诺塔
• 树的遍历
• 快速排序

11. 执行climb(6)的返回值为（ ）。

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

{{ select(11) }}

• 8
• 13
• 5
• 10

12. 下列关于递归的说法，正确的是（ ）。
{{ select(12) }}

• 递归函数必须包含循环
• 递归函数可以没有终止条件
• 递归函数调用自身
• 递归函数效率总是高于递推

13. 用递归实现斐波那契数列，n=40时，大约需要调用多少次？（ ）
{{ select(13) }}

• 40次
• 400次
• 约2^40次
• 约40^2次

14. 下面递归函数的功能是（ ）。

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

{{ select(14) }}

• 求n的阶乘
• 求1到n的和
• 求n的平方
• 求n的斐波那契

15. 下面递归函数，调用fun(4)的结果是（ ）。

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

{{ select(15) }}

• 24
• 10
• 4
• 1

---