【Python】斐波那契数列

2023-06-05 09:50| 来源: 网络整理| 查看: 265

递归法

递归函数就是在函数内部调用函数本身

def fibonacci(n): # 数列前两项为1和1，即F(1) = 1, F(2) = 1 if n == 1 or n == 2 : return 1 # 数列从第3项开始，每一项都等于前两项之和，即F(n) = F(n-1) + F(n-2) else: return fibonacci(n-1) + fibonacci(n-2)

代码简洁易读，但是运行效率低。n的数值过大，即递归次数过多时会出现内存溢出，报错：超出最大递归深度。RecursionError: maximum recursion depth exceeded in comparison。 Python 中递归的最大深度是1000。

递推法

使用循环，从前两项开始，逐个相加，直到求出第n个数的值。

# 使用for循环 def fib(n): # 数列前两项为1和1，即F(1) = 1, F(2) = 1 a, b = 1, 1 # 使用循环累加，循环n-2次。（range取值前闭后开） for i in range(n-1): # 从第二项开始，每次把后一项b的值赋值给a，成为下一次累加的前一项； # b计算当前最后两项的和，成为下次累加的后一项。 a, b = b, a + b # a的值为第n个数列的值，b的值已经为第n+1个数列的值。 return a # 使用while循环 def fib(n): a, b = 1, 1 while n > 1: a, b = b, a + b n -= 1 return a #注意 #a, b = b, a + b 写法正确。 #a = b，b = a + b 写法错误。 #a,b要同时赋值。如果b先赋值给a，b再计算a+b的值； #此时a的值已经为b，b=a+b相当于计算b+b的值，a的值就没有任何意义。

【本文地址】

公司简介

联系我们