斐波那契数列是一个经典的数学问题，其定义为：F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-2)（n≥2）。在编程中，我们可以通过多种方式来实现斐波那契数列的计算，包括递归和非递归方法。
递归实现：
1 def fib_recursive(n):
2 if n == 0:
3 return 0
4 elif n == 1:
5 return 1
6 else:
7 return fib_recursive(n - 1) + fib_recursive(n - 2)
8 print(fib_recursive(10))
递归方法虽然简洁直观，但由于存在大量的重复计算，导致其时间复杂度为O(2^n)，非常低效。
非递归实现：
1 def fib_iterative(n):
2 result = [0, 1]
3 for i in range(2, n + 1):
4 result.append(result[i - 1] + result[i - 2])
5 return result[n]
6 print(fib_iterative(10))
非递归方法通过迭代的方式避免了重复计算，时间复杂度为O(n)，显著提高了计算效率。
列出n以内的所有斐波那契数：
1 def list_fib_numbers(n):
2 a, b = 0, 1
3 while a <= n:
4 print(a, end=' ')
5 a, b = b, a + b
6 print()
7 list_fib_numbers(100)
为了进一步比较这两种方法的性能，我们可以使用Python的datetime模块来测量它们的执行时间。
1 import datetime
2
3 # 非递归方法测试
4 start_time = datetime.datetime.now()
5 print(fib_iterative(1000))
6 end_time = datetime.datetime.now()
7 print('Non-recursive execution time:', end_time - start_time)
8
9 print('*' * 30)
10
11 # 递归方法测试
12 start_time = datetime.datetime.now()
13 print(fib_recursive(40))
14 end_time = datetime.datetime.now()
15 print('Recursive execution time:', end_time - start_time)
从上述测试结果可以看出，非递归方法在处理大数值时表现出了显著的优势。例如，在计算第1000个斐波那契数时，非递归方法几乎瞬间完成，而递归方法在计算第40个斐波那契数时就已经需要数十秒的时间。
总结而言，虽然递归方法在代码上更为简洁，但在处理大规模数据时，非递归方法由于其更高的效率和更低的时间复杂度，是更加推荐的选择。
![[编程题] LeetCode上的Dynamic Programming(动态规划)类型的题目](https://img1.php1.cn/3cd4a/24cea/42f/ab7ad6031d31eee4.jpeg)
京公网安备 11010802041100号