递归开销——有多严重？

递归开销是一个严重的问题。我编写的大多数编程语言都会给函数调用带来实际的开销（它们的编译器通常也可以进行尾递归优化，所以有时不是问题）。

这种开销，以及栈不是无限资源的事实，通常使我倾向于仅在我知道深度有限的情况下使用递归。

例如，我知道一个平衡二叉树搜索只会在一千万条记录中遍历五十层。然而，我不会使用以下代码：

def sum1through (n):
    if n == 0 return 0
    return n + sum1through (n-1)

因为对于二千万的n来说，使用这个代码对栈来说是不健康的。

递归开销的主要原因是函数调用的成本以及栈空间的限制。栈是一个有限的资源，如果递归层数过深，会导致栈溢出错误。为了解决这个问题，我们可以考虑使用循环代替递归，或者使用尾递归优化。循环可以避免函数调用的开销，而尾递归优化可以使得递归调用不会增加栈的深度。

递归开销是一个需要关注的问题。在使用递归时，我们应该考虑到函数调用的成本和栈空间的限制，避免递归层数过深导致栈溢出错误的情况。如果可能的话，我们可以考虑使用循环或尾递归优化来减少递归开销。这样可以保证程序的性能和稳定性。

递归在以下情况下会导致显著的开销：如果递归函数的内核计算开销小于函数的入口/出口代码和函数调用本身的开销。要找出最佳方法，可以简单地对比两个版本的代码-一个是递归的，一个是非递归的。

如果你的避免递归的想法是自己创建一个类似堆栈的结构，请小心-它可能并不比更直接的递归方法快。同样，性能分析是你的朋友。

最后，请记住，程序员的时间比CPU的时间更宝贵。在对代码进行微观优化之前，最好先进行测量，看看是否真的会成为一个问题。

请注意，编译器现在有时可以将递归转化为简单的迭代循环，即使函数不是尾递归。查看linux-kongress.org/2009/slides/...。

如果有人成功地编写出比CPU自己的调用堆栈更高效的堆栈数据结构，我会非常惊讶...当然，可能有其他原因使用手动堆栈而不依赖调用堆栈，但性能永远不应该是其中之一。

事实上，已经有人做到了，例如glibc对qsort的实现（goo.gl/6ptK）-但是，这并不容易超越编译器，一个天真的尝试可能会带来更多的伤害而不是好处。

递归开销-有多严重？是什么导致了递归开销的产生以及如何解决？

递归占用大量的堆栈空间，每次方法调用自身时，都会生成一个指向该方法及其局部变量的指针。递归期间所进行的函数调用数量导致了O(n)的内存使用，而非递归函数（如循环）只需要O(1)的内存使用。

除非使用尾递归，并且使用理解尾递归的编程语言/编译器/平台，否则递归仍然存在。尾递归可以看作是一种编写循环的另一种方式。

递归的内存使用情况和递归深度有关。对于已知、有界的递归深度，这通常不是一个问题，因为在这种情况下，堆栈空间几乎不需要成本。

尽管尾递归与循环等效，但并不意味着编译器足够聪明以将它们视为等效。

尽管堆栈空间可能不会产生成本，因为它已经分配好了，但仍需要更多的物理内存。此外，将参数推送到堆栈上，保存寄存器以及其他一些必要的操作并不是免费的。

但由于该内存量是有界的，并且在其他地方不需要，这是无关紧要的。从所有目的来看，有界堆栈空间不占用任何内存。而且，与手动实现的堆栈相比，调用堆栈操作非常廉价。

内存是一种共享资源，每当实际引用内存时（这与为其“提供一个可用的内存地址”非常不同），就会与其他代码竞争RAM的空间（而不是换出到磁盘或未初始化）。而更重要的是，与缓存中的位置竞争。堆栈无疑比手动实现的堆栈更高效，但如果正确实现尾递归，根本不需要使用堆栈。

实际上，我曾考虑过在原始评论中写上“几乎不占用内存”，并提到缓存未命中，但我决定保持简洁。但很高兴看到我们在这方面有共识。