据我所知,由于函数调用的开销,递归函数通常效率低于等效的非递归函数.但是,我最近遇到了一本教科书,说
Java(和C#)并不是必需的.
它没有说明原因,但我认为这可能是因为Java编译器以某种方式优化了递归函数.
有谁知道为什么会这样的细节？
解决方法
这通常仅适用于尾递归(
http://en.wikipedia.org/wiki/Tail_call).
尾递归在语义上等同于递增的循环,因此可以优化为循环.以下是我链接到的文章的引用(强调我的)：
Tail calls are significant because
they can be implemented without adding
a new stack frame to the call stack.
Most of the frame of the current
procedure is not needed any more,and
it can be replaced by the frame of the
tail call,modified as appropriate.
The program can then jump to the
called subroutine. Producing such code
instead of a standard call sequence is
called tail call elimination,or tail call optimization. In functional programming languages,tail call elimination is often guaranteed by the language standard,and this guarantee allows using recursion,in particular tail recursion,in place of loops
