GESP 4级客观题｜递推｜课堂讲解

考试频率：高频。本卷共 2 题。

1. 下⾯关于递推的说法不正确的是（ ）。

   {{ select(1) }}

• 递推表现为⾃⼰调⽤⾃⼰
• 递推是从简单问题出发，⼀步步的向前发展，最终求得问题。是正向的
• 递推中，问题的n要求是在计算中确定，不要求计算前就知道n
• 斐波那契数列可以⽤递推实现求解

2. 以下代码⽤递推法求斐波那契数列的第$n$项，时间复杂度为指数级。

int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

    int f0 = 0; // F(0)
    int f1 = 1; // F(1)
    int current;

    for (int i = 2; i <= n; i++) {
	    current = f0+ f1; // F(n) = F(n-1) + F(n-2)
	    f0 = f1;
	    f1 = current;
    }
    return current
}

{{ select(2) }}

• 对
• 错