Fibonacci数列

在数学上，斐波纳契数列以如下被以递归的方法定义：F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）

1、Fibonacci数之二分递归：

算法实现：

int fib(int n)
{
    if(n <= 1)
        return 1;
    return fib(n - 1) + fib(n - 2);
}

算法分析：
二分递归版本的子问题f(n - 1) 与 fib(n - 2) 实际上并非彼此独立。

1. 时间复杂度：
   二分版本的时间复杂度高达O(2^n)，究其原因在于，计算过程中所出现的递归实例的重复度极高。
2. 空间复杂度：
   O(logn)

算法优化分析：
为消除递归算法中重复的递归实例，一种自然而然的思路和技巧，可以概况为：
借助一定量的辅助空间，在各个子问题求解之后，及时记录下其对应的解
比如，可以从原问题出发自顶而下，每遇到一个子问题，都首先查验它是否已经计算过，以期通过调阅记录获得解答，从而避免重复计算。这种策略被称为制表（tabulation）或记录（memoization）。

2、Fibonacci数之制表

算法思路：
使用二分递归模式，完全是因为受到该问题原始定义的表面特征——fib(n)由 fib(n - 1) 和 fib(n - 2) 共同决定——的误导。然后不难看出，子问题 fib(n - 1) 和 fib(n - 2) 实际上并非彼此独立。比如，只要转而采用定义如下的递归函数，计算一对相邻的Fibonaaci数：

(fib(k - 1), fib(k))

算法实现：

__int64 fib(int n, __int64 &prev)
{
    if(0 == n)
    {
        prev = 1;
        return 0;
    }
    else
    {
        __int64 prevPrev;
        prev = fib(n - 1, prevPrev);
        return prevPrev + prev;
    }
}

算法分析：

1. 时间复杂度：
   该算法呈线性递归模式，递归深度线性正比于输入n，前后共计出现O(n)个递归实例，时间复杂度为O(n)。
2. 空间复杂度：
   遗憾的是，该算法共需使用O(n)规模的附加空间。

算法优化分析：
反观制表版本的fib()算法可见，其中所记录的每一个子问题的解答，只会用到一次，在该算法抵达递归基之后的逐层返回过程中，每向上返回一层，以下各层的解答均不必继续保留。

3、Fibonacci数之动态规划

算法思路：
若将以上逐层返回的过程，等效地视作从递归基出发，按规模自小而大求解各子问题的过程，即可采用动态规划的策略。

算法实现：

__int64 fib(int n) 
{
    __int64 f = 0, g = 1;
    while (0 < n--) 
    { 
        g += f; 
        f = g - f; 
    }
    return f;
}

算法分析：

1. 时间复杂度：
   O(n)
2. 空间复杂度：
   O(1)，出于空间考虑，应尽量将递归改写为迭代模式。