递归开销-有多严重?[副本]

如果递归函数的内核比函数入口/出口代码的计算开销和调用本身的开销小,递归可能会导致很大的开销。最好的方法是简单地分析代码的两个版本-一个是递归的,另一个不是。

也就是说,如果避免递归的想法是自己创建一个类似堆栈的结构,请注意-它可能并不一定比更直接的递归方法快。同样,分析是你的朋友。

很严重。我编写的大多数语言的函数调用都有实际成本(它们的编译器通常也可以进行尾部递归,所以有时这不是问题)。

例如,我知道一个平衡的二叉树搜索对于一个百万分之一的条目只会深入50层。但是,我不会使用:

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

因为那样做是为了 n 两千万对一堆人来说是不健康的。

我不认为你提到的任何一种语言 要求 平台/编译器实现 tail call elimination . 你可以找到 需要这种优化-大多数函数式语言都有这种要求。

不过,你还需要考虑的另一件事是,计算机比15年前更快地成为数量级,因此在那之前,你需要担心微观优化的情况要少得多。一个15年前可能需要在汇编程序中进行仔细的手工优化才能获得良好性能的程序,即使是用像Java这样的高级语言编写的,也可能在现代计算机上运行得非常快。这并不是说性能不再是一个问题,但是您应该集中精力选择 正确的算法 可读的

有件事你 做 不过,需要担心的是堆积如山。如果有发生这种情况的风险,那么用迭代的方式重写递归函数可能是值得的。

人们对表演说了很多傻话。

1. 需要 递归,喜欢先做深度树遍历,然后你需要它,所以使用它。

2. 任何东西
   性能问题就像骗子和骗子——他们专门做你最不期望的事情,所以如果你担心某些特定的事情,比如递归,你几乎肯定会担心错误的事情。

在我看来,发现性能问题的最佳方法是堆栈采样 ,和 examining the samples to see what the program is doing ,不仅仅是通过测量和思考它们的含义。