在数学上，斐波纳契数列以如下被以递归的方法定义：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) 实际上并非彼此独立。
- 时间复杂度：
二分版本的时间复杂度高达O(2^n)，究其原因在于，计算过程中所出现的递归实例的重复度极高。 - 空间复杂度：
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;
}
}
算法分析：
- 时间复杂度：
该算法呈线性递归模式，递归深度线性正比于输入n，前后共计出现O(n)个递归实例，时间复杂度为O(n)。 - 空间复杂度：
遗憾的是，该算法共需使用O(n)规模的附加空间。
算法优化分析：
反观制表版本的fib()算法可见，其中所记录的每一个子问题的解答，只会用到一次，在该算法抵达递归基之后的逐层返回过程中，每向上返回一层，以下各层的解答均不必继续保留。
3、Fibonacci数之动态规划
算法思路：
若将以上逐层返回的过程，等效地视作从递归基出发，按规模自小而大求解各子问题的过程，即可采用动态规划的策略。
算法实现：
__int64 fib(int n)
{
__int64 f = 0, g = 1;
while (0 < n--)
{
g += f;
f = g - f;
}
return f;
}
算法分析：
- 时间复杂度：
O(n) - 空间复杂度：
O(1)，出于空间考虑，应尽量将递归改写为迭代模式。
