296 斐波那契数列1 #
- 斐波那契数列
- 斐波那契数列的递归实现
斐波那契数列 #
斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：
f(1)=0，f(2)=1, f(n)=f(n-1)+f(n-2)(n ≥ 3)。
从递归的关系式可以看出，该数列只需要最初的几项就可以计算得到后续的任意项的数值。
f(1)=0，f(2)=1, f(n)=f(n-1)+f(n-2)(n ≥ 3)。
从递归的关系式可以看出，该数列只需要最初的几项就可以计算得到后续的任意项的数值。
斐波那契数列数列的递归实现 #
首先考虑斐波那契数列的递归关系,fib(n)的值始终由前两项计算得到
def fib(n):
out=fib(n-1) + fib(n-2)
return out
当n<=1时，不存在比n更小的两项，这时存在递归的结束条件
def fib(n):
if(n<2):
return n
下面是完整的斐波那契数列实现
def fib(n):
if(n<2):
return n
return fib(n-1) + fib(n-2)
可以看到，使用递归实现斐波那契数列非常简洁
小结 #
习题 #
- 详细描述斐波那契数列递归调用的过程
- 体会递归算法的优点
