fibonacci算法使用数组实现

Question

为什么要使用数组，数组在每次调用方法递归时都会重新实例化一个新的数组，数组中元素也是默认的，那么递归条件
数组的意义在哪里，以及fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];这条语句的作用是什么，
为什么要返回一个数组而不是直接返回一个递归结束的结果数值呢？

public class Fibonacci {
    public static long[] F(int N) {
        long[] fibonacci = new long[N + 1];
        if (N == 0) {
            return fibonacci;
        }
        fibonacci[1] = 1;
        if (N == 1) {
            return fibonacci;
        }
        for (int i = 2; i <= N; i++) {
            fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
        }
        return fibonacci;
    }

    public static void main(String[] args) {
        long[] fibonacci = F(99);
        for (int N = 0; N < fibonacci.length; N++) {
            StdOut.println(N + " " + fibonacci[N]);
        }
    }
}

Answer 1

上面的fibonacci的实现是dynamic programming动态规划算法，并不是递归实现的。
下面这个才是递归实现的fibonacci

long int Fibonacci_0( unsigned int n)
{
    if(n<=2)
     return 1;
     else
     return Fibonacci_0(n-1) + Fibonacci_0(n-2);
};

这个递归算法就是直接返回值，而动态规划算法简单来说就是把之前求出来的值记录下来保存在数组中，在计算下个值需要用到已知值的时候拿出来，而不是重新计算

所以动态规划可以节省非常多的计算时间
比如：
1. 递归计算fibonacci(4) = fibonacci(3) + fibonacci(2)；
1. 先计算前面的fibonacci(3)；
1. 接下来要计算fibonacci(3) = fibonacci(2) + fibonacci(1)；
1. 然后是fibonacci(2) = fibonacci(1) + fibonacci(0)；
1. 再计算后面的fibonacci(2)；
1. fibonacci(2) = fibonacci(1) + fibonacci(0)；

可以发现里面的重复计算非常多，数字越大所花的开销和重复计算的次数越多。
在此基础上，动态规划用数组保存了之前计算过的值：如你提出的：

• fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2]