这是python中一个众所周知的问题，递归涉及大量开销。 如此之多，以至于即使是相对较浅的递归调用也会导致程序崩溃。 一种可能的解决方法是用 C 语言实现花哨的递归算法，并提供 python 钩子。 然而，众所周知，算法的递归实现几乎无论如何都比循环更昂贵，除非你的编译器认识到一些非常具体的机会(如尾递归)来循环整个业务。
Anyhoo，由于递归涉及函数调用的开销，我想知道 python 与 C 中函数调用(以及递归)的相对费用是多少？ 我知道我可以timeit，但我希望得到一个有原则的解释。 python函数调用与C函数调用有什么关系？ 此外，python 和 C 之间的函数调用堆栈是否存在差异，从而影响深度调用堆栈的性能？
你从一组错误的前提开始：
在python中，递归涉及大量开销是一个众所周知的问题。
不，不是。递归函数调用的开销与任何其他函数调用的开销基本相同。可能有一个很小的区别，即您不断分配新的堆栈帧并将它们加载到缓存中，而使用内部具有非递归调用的循环实现的相同内容将能够重用相同的堆栈帧。但这将是非常小的。
如此之多，以至于即使是相对较浅的递归调用也会导致程序崩溃。
不，他们没有。深度超过 1000 的递归完全失败，并出现异常。这部分是为了防止此类崩溃，但也是为了更容易检测意外的无限递归。
一种可能的解决方法是在 C 语言中实现花哨的递归算法
这无济于事。大多数 C 实现处理递归的方式与大多数 Python 实现基本相同(事实上。在CPython中，递归可以只是C递归主评估循环的问题)。仍然没有尾部调用消除，没有特殊处理来仅保持帧中的实时变量处于活动状态等。虽然C堆栈帧比Python框架小一点，但这只是一个很小的乘法因子。
同时，与Python程序不同，如果你递归太深，C程序实际上会崩溃。
当然，当你做的是低级计算时，C 代码确实比 Python 代码快一两个数量级，这将像其他任何地方一样帮助你(尽管可能不像平时那么多，因为 C 中的函数调用虽然不像 Python 那么慢， 仍然远非免费)。另外，C 确实迫使你在某些事情上更明确——例如，没有闭包，所以如果你想要nonlocal的效果，你需要将指针传递给局部变量——这可能会导致你优化你在 Python 中不会想到的东西。
但总的来说，这里的好处比非递归代码少的话。
在某些情况下，一个好的 C 优化器可以看到整个帧是无用的并放弃它。在某些情况下，它甚至可以完全消除尾部调用。这不如您可以依靠的通用尾叫消除来确保正确性，但它肯定是有帮助的。
但是一个好的 JIT 优化器有时可以做同样的事情。在 PyPy 或 Jython 中运行现有代码肯定比用 C 重写它简单得多。
(我相信在某些情况下，例如，LLVM 的 AOT 优化器可以提供帮助，但 PyPy 的 JIT 不能，但我也怀疑任何能够可靠地猜测这些情况的人都不会首先问这个问题。
有些语言比Python和C更好地处理递归。
如果你用Haskell编写算法，然后将其包装在一个C API中，你可以通过ctypes或通过用C编写的简单扩展调用(或者甚至只是将其编译为程序并对其进行子处理，如果你谈论的是需要几秒钟才能运行的东西);那会起作用。
但是，如果你将递归重写为具有显式堆栈的循环，你将消除与在并非旨在鼓励递归的语言(即 Python 和 C)中使用递归相关的所有问题，并为其他优化打开大门。
例如，您(或LLVM的优化器，或PyPy的JIT)可以在内部循环的中间内联函数调用，这显然不能通过递归调用来实现。
此外，提取代码片段通常变得更容易，而不必跨 Python 边界来回调用，因此您可以将瓶颈移植到 C 扩展模块，而无需移植整个内容。