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

问题1就是保存了中间结果
问题2我也不肯定，我猜这个运算时间也是斐波那契数列
问题3的f(N)==0是用来判断这个值有没有计算过的，计算过直接调用已保存的结果，没计算过的f(N)是0，就进行if立面的计算
问题4是long长度越界了

Answer 2

保存中间计算结果，避免重复计算

Answer 3

你可以上网去查查尾递归的概念，这个其实就是编译器的优化而已。
http://www.cnblogs.com/JeffreyZhao/archive/2009/04/01/tail-recursion-e...