为什么递归功能消耗的处理时间比循环多？
为什么递归功能消耗更多的处理时间比循环？而且，对于处理器来说，这是否繁琐？
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
print fibonacci(40)这个例子需要大约1分钟，但循环只有几毫秒
如果向它添加了一个备忘录缓存，它将快速完成。 我运行此代码
def fib(n):
fib.count += 1
if n < 2:
return 1
else:
return fib(n-2) + fib(n-1)
fib.count = 0
print(fib(40))
print(fib.count)然后我运行此代码，使用字典保存和重复使用部分结果：def fib(n):
fib.count += 1
a = partial_results.get(n, None)
if a is None:
a = fib(n-2) + fib(n-1)
partial_results = a
return a
partial_results = {0:0, 1:1}
fib.count = 0
print(fib(40))
print(fib.count)这类似于 Python 使用缓存为您所做的，但扩展了，以便您可以看到该机制。结果是相同的，但纤维功能只被称为79次。如果我要计算多个斐波纳契数字，其中许多可以通过单个调用fib来计算。
因此，原始递归需要更长的时间，因为它正在做一个荒谬的功能调用计算相同的结果一遍又一
遍。 从一个非常简单的情况下开始：
fib = fib +
fib fib = （fib = fib + fib ） =
（fib = fib = fib fib = （fib = （fib = fib
= fib ） = fib ） = （fib = fib = fib ） 这是 9 个调用 fib （）。
此代码记录了每个值 n 的调用
次数：calls = {}
def fib(n):
calls = calls.get(n, 0) + 1
if n < 2:
return 1
else:
return fib(n-1) + fib(n-2)
fib(5)
for n, count in calls.items():
print(f'{n:3d} : {count:5d}')
print('Total', sum(calls.values())) 我想你的循环写得不完全一样。
递归表示功能调用。功能调用将需要更多的时间和内存，而不仅仅是执行一个循环。但差别并不大。
但是你的程序写的方式，你重写你的工作一遍又一
遍。我猜你的循环不是用那种方式写的缓慢性是由于算法，而不是本质上的递归。
如果向它添加了一个备忘录缓存，它将快速完成。from functools import lru_cache
@lru_cache
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(40))
页:
[1]