斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波纳契数列以如下被以递归的方法定义:F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=2,n∈N*)
- 递归实现
# 递归法实现斐波那契数列
import time
time_start = time.time()
def fibonacci_recursion(n):
assert n>=0
if n <= 1:
return n
return fibonacci_recursion(n-1)+fibonacci_recursion(n-2)
for i in range(1, 20):
print(fibonacci_recursion(i))
time_end = time.time()
print('运行时间:',time_end-time_start)
- 递增实现
# 递推实现斐波那契数列
import time
time_start = time.time() #计时
#########################
def fibonacci_loop(n):
a,b = 1,1
while n>0:
a,b = b,a+b
n -= 1
return a
for i in range(20):
print(fibonacci_loop(i))
#########################
time_end = time.time() #计时
print('运行时间:',time_end-time_start)