本文介绍了为什么Python递归如此昂贵？我们能做些什么呢？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
假设我们要计算一些模为997的斐波纳契数。
对于n=500，我们可以在C++中运行
#include <iostream>
#include <array>
std::array<int, 2> fib(unsigned n) {
if (!n)
return {1, 1};
auto x = fib(n - 1);
return {(x[0] + x[1]) % 997, (x[0] + 2 * x[1]) % 997};
}
int main() {
std::cout << fib(500)[0];
}
和在Python中
def fib(n):
if n==1:
return (1, 2)
x=fib(n-1)
return ((x[0]+x[1]) % 997, (x[0]+2*x[1]) % 997)
if __name__=='__main__':
print(fib(500)[0])
两者都将毫无问题地找到答案996。我们正在使用模数来保持合理的输出大小，并使用对来避免指数分支。
对于n=5000，C++代码输出783，但Python将出现错误
RecursionError: maximum recursion depth exceeded in comparison
如果我们添加几行
import sys
def fib(n):
if n==1:
return (1, 2)
x=fib(n-1)
return ((x[0]+x[1]) % 997, (x[0]+2*x[1]) % 997)
if __name__=='__main__':
sys.setrecursionlimit(5000)
print(fib(5000)[0])
然后，Python也会给出正确的答案。
forn=50000当Python崩溃时(至少在我的计算机上)，C++在毫秒内找到答案151。
为什么递归调用在C++中要便宜得多？我们是否可以通过某种方式修改Python编译器，使其更易于接受递归？
当然，一种解决方案是用迭代代替递归。对于斐波纳契数来说，这很容易做到。然而，这将交换初始条件和终止条件，而后者对于许多问题(例如，阿尔法-贝塔修剪)来说是棘手的。因此，一般来说，这将需要程序员进行大量艰苦的工作。推荐答案
解决方案是一个蹦床：递归函数不是调用另一个函数，而是返回一个函数，该函数使用适当的参数进行调用。有一个更高一级的循环，它在一个循环中调用所有这些函数，直到我们得到最终结果。我可能没有很好地解释它；您可以在网上找到更好的资源。
关键是这会将递归转换为迭代。我不认为这更快，也许更慢，但递归深度仍然很低。实现可能如下所示。为清楚起见，我将x拆分为a和b。然后，我将递归函数转换为跟踪a和b作为参数的版本，使其成为尾递归函数。
def fib_acc(n, a, b):
if n == 1:
return (a, b)
return lambda: fib_acc(n - 1, (a+b) % 997, (a+2*b) % 997)
def fib(n):
x = fib_acc(n, 1, 2)
while callable(x):
x = x()
return x
if __name__=='__main__':
print(fib(50000)[0])
这篇关于为什么Python递归如此昂贵？我们能做些什么呢？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！
本站部分内容来源互联网,如果有图片或者内容侵犯您的权益请联系我们删除！