1.考察来源
是由算法与数据结构中的递归和循环引申而来的。需要重复多次的计算相同问题，通常可以选择用递归或者是循环两种不同的方法。
递归是在一个函数的内部调用这个函数自身。
循环是通过设置计算的初始值与终止条件，在一个范围内反复运算。
通常递归的代码会比较简介，如果没有过多的要求应该多次啊用递归的方法编程。
递归虽然由简洁的优点，但是它同时有显著的缺点。递归由于函数调用自身，而函数调用是有时间和空间的消耗的（每一次函数调用都需要在内存栈中分配空间保存参数，返回地址及临时变量，而且往栈里压入数据和弹出数据都需要时间），递归实现的效率不如循环。
递归中有可能很多计算都是重复的，给性能带来很大的负影响。因为递归的本质是将一个问题分解成多个小问题，多个小问题存在相互重叠的部分，就是重复的计算。
除却效率之外，递归可能引起更严重的问题：调用栈溢出，当递归调用层级太多时，就会超出栈的容量。
2.问题的描述
$F _ { n } = \left{ \begin{array} { l l } { 0 , } & { ( n = 0 ) } \ { 1 , } & { ( n = 1 ) } \ { F _ { n - 1 } + F _ { n - 2 } , } & { ( n > 1 ) } \end{array} \right.$
教科书中关于此问题的递归解答为：
long long Fibonacci(unsigned int n)
{
if (n<=0)
return 0;
if (n==1)
return 1;
return Fibonacci(n-1)+Fibonacci(n-2);
}
将当前所求的值，从上到下拆分，知道n=0或者n=1时，再重新返回来从低进行计算得到最终的值。
n=4时，分解为求n=3,n=2的值
n=3,分解为n=2和n=1
n=2分解为n=1和n=0,得到具体的值
n=2分解为n=1和n=0，得到具体的值
其中的第一步的分解的节点和第二步的第一部分分解的节点造成的重复。这种重复的节点数会随着$n$的增大而急剧增加。
3. 使用解法
改进的主要工作是避免重复计算。所以简单的办法就是从下到上的进行计算。从0和1计算出2，再计算出3这样推算出$n$项 的值，时间复杂度为$O(n)$，实现代码如下：
class Solution:
def Fibonacci(self, n):
# write code here
# 直接递归会超时，需要使用动态规划的思想
res = [0, 1]
while len(res) <= n:
res.append(res[-1] + res[-2])
return res[n]
#或者 我的提交
# -*- coding:utf-8 -*-
class Solution:
def Fibonacci(self, n):
# write code here
res = [0,1]
if n<2:
return res[n]
nOne = 0;
nTwo = 1;
for _ in range(1,n):
nOne,nTwo = nTwo,nOne+nTwo
return nTwo
4. 问题变形
很多题可以看作是斐波那契数列的应用。
-
青蛙跳台阶问题
一只青蛙一次可以跳1级台阶，也可以跳2级台阶，求该青蛙跳上一个n级台阶总共有多少种跳法
最简单的情况，如果只有1级台阶，显然只有以中跳法，如果有2级台阶，就有两种跳法，一种是每次跳1级，一次是一次跳2级.
当$n>2$时，第一次跳就有两种不同的选择：第一种是第一次跳1级，此时跳法数据等于剩余$n-1$级台阶的跳法数目，第二种是第一次跳2级，变成了$n-2$ 级台阶的跳法数目了。此时$n$级台阶的不同跳法数目为：$f(n)=f(n-1)+f(n-2)$，这就符合斐波那契数列了
