[已解决]为什么递归功能消耗的处理时间比循环多？

意乱情迷

为什么递归功能消耗更多的处理时间比循环？
而且，对于处理器来说，这是否繁琐？

1. def fibonacci(n):
   
2.     if n == 0:
   
3.         return 0
   
4.     elif n == 1:
   
5.         return 1
   
6.     else:
   
7.         return fibonacci(n-1) + fibonacci(n-2)
   
8. 
   
9. print fibonacci(40)

复制代码

这个例子需要大约1分钟，但循环只有几毫秒

最佳答案

珍惜相遇

2021-5-31 11:07:07

我想你的循环写得不完全一样。
递归表示功能调用。功能调用将需要更多的时间和内存，而不仅仅是执行一个循环。但差别并不大。
但是你的程序写的方式，你重写你的工作一遍又一
遍。我猜你的循环不是用那种方式写的缓慢性是由于算法，而不是本质上的递归。
如果向它添加了一个备忘录缓存，它将快速完成。

1. from functools import lru_cache
   
2. 
   
3. @lru_cache
   
4. def fibonacci(n):
   
5.     if n == 0:
   
6.         return 0
   
7.     elif n == 1:
   
8.         return 1
   
9.     else:
   
10.         return fibonacci(n-1) + fibonacci(n-2)
    
11. 
    
12. print(fibonacci(40))

复制代码

跳转到最佳答案楼层

北京土人

如果向它添加了一个备忘录缓存，它将快速完成。

他来自江湖

我运行此代码

1. def fib(n):
   
2.     fib.count += 1
   
3.     if n < 2:
   
4.         return 1
   
5.     else:
   
6.         return fib(n-2) + fib(n-1)
   
7. 
   
8. fib.count = 0
   
9. print(fib(40))
   
10. print(fib.count)

复制代码

然后我运行此代码，使用字典保存和重复使用部分结果：

1. def fib(n):
   
2.     fib.count += 1
   
3.     a = partial_results.get(n, None)
   
4.     if a is None:
   
5.         a = fib(n-2) + fib(n-1)
   
6.         partial_results[n] = a
   
7.     return a
   
8. 
   
9. partial_results = {0:0, 1:1}
   
10. fib.count = 0
    
11. print(fib(40))
    
12. print(fib.count)

复制代码

这类似于 Python 使用缓存为您所做的，但扩展了，以便您可以看到该机制。结果是相同的，但纤维功能只被称为79次。如果我要计算多个斐波纳契数字，其中许多可以通过单个调用fib来计算。
因此，原始递归需要更长的时间，因为它正在做一个荒谬的功能调用计算相同的结果一遍又一
遍。

雪在烧

从一个非常简单的情况下开始：
fib [4] = fib [3] +
fib [2] fib [4] = （fib [3] = fib [2] + fib [1] ） =
（fib [2] = fib [1] = fib [0] fib [4] = （fib [3] = （fib [2] = fib [1]
= fib [0]） = fib [1]） = （fib [2] = fib [1] = fib [0]） 这是 9 个调用 fib （）。
此代码记录了每个值 n 的调用
次数：

1. calls = {}
   
2. 
   
3. def fib(n):
   
4.     calls[n] = calls.get(n, 0) + 1
   
5.     if n < 2:
   
6.         return 1
   
7.     else:
   
8.         return fib(n-1) + fib(n-2)
   
9. fib(5)
   
10. for n, count in calls.items():
    
11.     print(f'{n:3d} : {count:5d}')
    
12. print('Total', sum(calls.values()))

复制代码

珍惜相遇

我想你的循环写得不完全一样。
递归表示功能调用。功能调用将需要更多的时间和内存，而不仅仅是执行一个循环。但差别并不大。
但是你的程序写的方式，你重写你的工作一遍又一
遍。我猜你的循环不是用那种方式写的缓慢性是由于算法，而不是本质上的递归。
如果向它添加了一个备忘录缓存，它将快速完成。

1. from functools import lru_cache
   
2. 
   
3. @lru_cache
   
4. def fibonacci(n):
   
5.     if n == 0:
   
6.         return 0
   
7.     elif n == 1:
   
8.         return 1
   
9.     else:
   
10.         return fibonacci(n-1) + fibonacci(n-2)
    
11. 
    
12. print(fibonacci(40))

复制代码