python vs C中的递归开销[closed]

你是从一组错误的前提开始的:

递归涉及大量开销,这是python中一个众所周知的问题。

不,不是。递归函数调用的开销与任何其他函数调用的开销基本相同。可能会有一个小的区别,那就是你一直在分配新的堆栈帧并将它们加载到缓存中,而用一个内部有非递归调用的循环实现的相同的东西将能够重用相同的堆栈帧。但这将是相当小的。

如此之多,以至于即使是相对较浅的递归调用也会导致程序崩溃。

不,他们没有。深度超过1000的递归完全失败,并出现异常。这在一定程度上是为了防止此类崩溃,同时也使检测意外的无限递归变得更容易。

这没什么用。大多数C实现处理递归的方式与大多数Python实现基本相同(事实上。在CPython中,递归只是C递归主eval循环的问题)。仍然没有尾部调用消除,没有特殊的处理来保持一个帧的活动变量,等等。虽然C堆栈帧比Python堆栈帧小一些,但这只是一个小的乘法因子。

将 如果你递归太深就崩溃。

nonlocal 您需要将指针传递到locals,这可能会导致您在Python中优化您不想优化的内容。

但一般来说,这里的好处比不上非递归代码。

但是一个好的JIT优化器有时也可以做同样的事情。用PyPy或Jython运行现有代码肯定比用C重写要简单得多。

(我确信会有一些情况,例如LLVMs AOT优化器可以提供帮助,但PyPys JIT不能,但我也怀疑,任何能够可靠地猜测这些情况的人都不会首先问这个问题。)

在那里 是

如果将算法编码到Haskell中,然后将其包装到一个可以通过 ctypes

但是,如果您改为使用显式堆栈将递归重写为循环,那么您将消除与使用递归相关的所有问题,而使用的语言并不是为鼓励递归而设计的(即Python和C),并为其他优化打开大门。

例如,您(或LLVMs优化器,或PyPys JIT)可以在内部循环的中间内联函数调用,这显然是递归调用所不能做到的。

而且,在不需要跨Python边界来回调用的情况下提取代码片段通常会变得更容易,因此可以将瓶颈移植到C扩展模块,而不必移植整个代码。