为什么 Python 递归如此昂贵，我们能做些什么呢？
假设我们要计算一些斐波那契数，模997。
对于 C + + 中的 n=500，我们可以运行
#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];
}
还有巨蟒
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 也会给出正确的答案。
因为当 Python 崩溃时(至少在我的机器上) ，n=50000 C + + 在毫秒内找到答案151。
为什么在 C + + 中递归调用要便宜得多？我们能够以某种方式修改 Python 编译器，使其更容易接受递归吗？
当然，一种解决方案是用迭代代替递归。对于斐波那契数，这是很容易做到的。然而，这将交换初始条件和终端条件，而后者对于许多问题来说是棘手的(例如 alpha-beta 修剪)。所以一般来说，这需要程序员做大量的艰苦工作。
最佳答案