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)
可以看到,使用递归实现斐波那契数列非常简洁
小结 #
习题 #
- 详细描述斐波那契数列递归调用的过程
- 体会递归算法的优点