斐波纳契数列(Fibonacci Sequence)，又称黄金分割数列，指的是这样一个数列: 1、1、2、3、5、8、13. 21. ....在数学上，斐波纳契数列以如下被以递归的方法定义: F0=0， F1=1, Fn=F(n-1)+F(n-2) (n>=2， n∈N*)。
第一种方法是递归算法(是最普遍的解决算法)，这种算法的时间复杂度很高。因为在计算fb(n-1)的时候，把fib(n-2)也给计算了一遍。这样资源得不到重复利用。时间复杂度是指数级的。
第二种方法是递推法，利用递推算法求问题规模为n的解的基本思想是：当n=1时，解或为已知，或能非常方便地求得；通过采用递推法构造算法的递推性质，能从已求得的规模为1. 2、... i-1的一系列解，构造出问题规模为的解。这样，程序可从i=0或i=1出发，重复地由已知至i-1规模的解，通过递推，获得规模为的解，直至获得规模为n的解。