斐波那契数列两种实现

斐波那契数列是由 0 和 1 开始，后面的每一项是前面两项的和，即 0、1、1、2、3、5、8、13、21、34……
两种实现方法如下：

递归实现

def fibonacci_recursive(n):
if n <= 1:
return n
return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)
登录后复制

迭代实现

def fibonacci_iterative(n):
if n <= 1:
return n
fib = [0, 1]
for i in range(2, n+1):
fib.append(fib[i-1] + fib[i-2])
return fib[n]
登录后复制

相关问题

用python实现斐波那契数列两种方法并分析优缺点

方法一：递归实现斐波那契数列
def fibonacci_recursive(n):
if n <= 1:
return n
else:
return (fibonacci_recursive(n-1) + fibonacci_recursive(n-2))
登录后复制
优点：代码简洁易懂，逻辑清晰。
缺点：递归调用会导致性能较差，在计算较大的斐波那契数列时容易出现栈溢出的问题。
方法二：循环实现斐波那契数列
def fibonacci_loop(n):
if n <= 1:
return n
else:
a, b = 0, 1
for i in range(2, n+1):
c = a + b
a, b = b, c
return b
登录后复制
优点：循环实现的性能比递归实现更好，在计算较大的斐波那契数列时不容易出现栈溢出的问题。
缺点：代码相对于递归实现稍微复杂一些，需要使用循环控制语句。
综上所述，循环实现的斐波那契数列比递归实现更优，因为它具有更好的性能和更小的风险。

斐波那契数列两种算法的时间复杂度

斐波那契数列是指这样一个数列：0、1、1、2、3、5、8、13、……，后面的每一项都是前面两项的和。有两种常见的计算斐波那契数列的算法：

递归法：
这种方法直接通过定义数列的递推关系来实现，但是由于每个数都需要基于前两个数计算，存在大量的重复计算。时间复杂度是 O(2^n)，其中 n 是需要计算的第 n 个数，效率较低。
def fib_recursive(n):
if n <= 1:
return n
else:
return fib_recursive(n-1) + fib_recursive(n-2)
登录后复制

动态规划法（记忆化搜索）：
使用缓存（如数组或字典）存储已经计算过的值，避免了重复计算，将时间复杂度降低到线性。时间复杂度为 O(n)，因为只遍历一次数列。
def fib_dynamic(n, memo={}):
if n in memo:
return memo[n]
elif n <= 1:
result = n
else:
result = fib_dynamic(n - 1, memo) + fib_dynamic(n - 2, memo)
memo[n] = result
return result
登录后复制