g4-03947. GESP-4级-2024-09-判断-第09题 未做

以下代码用递推法求斐波那契数列的第 $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;
}