java - 为什么这样写显著提升了Fibonacci sequence性能？？

Question

问题来自Algorithms(算法，第四版)的1.1.19练习题。
题目如下：

在计算机上运行一下程序：

Javapublic class Fibonacci {
    public static long F(int N)  {
        if (N == 0)
            return 0;
        if (N == 1) 
            return 1;
        return F(N-1) + F(N-2);
    }
    public static void main(String[] args)  {
        for (int N = 0; N < 100; N++)
            StdOut.println(N + " " + F(N));
    }
}

计算机用这段程序在一小时内能得到的F(N)结果的最大N值是多少？开发F(N)的一个更好的实现，用数组保存已经计算的值。

---------题目结束--------------

首先我在计算机上(windows8.1 64位系统)运行上面程序，如下：

发现用上面题目给出的方法运行到N = 40多时，程序已经明显慢下来了，

问题1：慢下来是因为处理的数据太大了，而且每次都要再次计算？还是因为其他什么原因？
问题2：题目中要预测计算机在一小时内能够得到F(N)结果的最大N值，这个怎么做？

然后在这里提供了题目问题的代码，如下：

javapublic class Ex_1_1_19
{
    public static long F(int N)
    {
        if (N == 0) return 0;
        if (N == 1) return 1;
        return F(N-1) + F(N-2);
    }

    public static long Fib(int N)
    {
        long[] f = new long[N+1];
        return Fib(N, f);
    }

    public static long Fib(int N, long[] f)
    {
        if (f[N] == 0)
        {
            if (N == 1)
                f[N] = 1;
            else if (N > 1)
                f[N] = Fib(N-1, f) + Fib(N-2, f);
        }

        return f[N];
    }

    public static void main(String[] args)
    {
//        for (int N = 0; N < 100; N++)
//            StdOut.println(N + " " + F(N));
        for (int N = 0; N < 100; N++)
            StdOut.println(N + " " + Fib(N));
    }
}

再次运行时，居然在1秒多就运行完了:

问题3：
很好奇为什么这么快，自己尝试分析下，用N=0,1,2,3试，但是在Fib函数中为什么要if (f[N] == 0)呢？数组最后一个元素为0？
是因为用数组 f 保存已经计算过的值了，所以不需要再重新计算了所以才快了很多吗？
问题4：
最后结果从93行开始，93,95，96,97,99行出现的负数，大致知道是和操作系统运算有关，但又不是很清楚，求解释？

Answer 1

Problem 1 is to save the intermediate results
I’m not sure about question 2 either. I guess the calculation time is also the Fibonacci sequence
The f(N)==0 in question 3 is used to determine whether the value has been calculated. If it has been calculated, the saved result is directly called. If the uncalculated f(N) is 0, then the calculation of the if facade is performed
Problem 4 is that the length of long is out of bounds

Answer 2

Save intermediate calculation results to avoid repeated calculations

Answer 3

You can go online to look up the concept of tail recursion. This is actually just the optimization of the compiler.
http://www.cnblogs.com/JeffreyZhao/archive/2009/04/01/tail-recursion-e...