A31064. 以下代码用递推法求斐波那契数列的第 项，时间复杂度为指数级。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; …

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

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;
}