5

Are there any tail call optimizations possible besides tail recursion? I've been trying to find or think of one that doesn't involve recursion, but with no success. Is it possible? Any examples?

4

2 回答 2

3

当然，“尾调用优化”实际上是这种优化的最一般的、与递归无关的形式。这种优化不会用等效的while循环或类似的东西代替递归。相反，尾调用被转换，使得调用者的堆栈帧被重新使用。任何形式的代码return f(...)或f(...); return都可以对此进行修改。它适用于any f，甚至适用于编译器不可能知道正在调用什么的函数指针/闭包/虚拟方法。因此，它也适用于单独编译、高阶函数、后期绑定等。

如果您查看足够多的代码，无论是功能性的还是命令性的，您会发现偶尔的调用没有任何后续。一个常见的情况是调用者将主要任务委托给被调用者并且只做一些额外的准备工作。在函数式代码中，您经常会发现许多只做一件事并根据其他小函数实现的小函数，因此您最终需要对参数应用简单的转换，然后执行尾调用下一层（以转换后的数据作为参数）。TCO 优化了第二步，它（理想情况下）使调用像简单的一样便宜jump并使漂亮的模块化代码与更单一的实现相比占用更少的堆栈空间。在面向对象的设计中，您可能希望组合其他对象的对象并公开委托的便捷方法：

SomeClass doSomething(Argument a) {
    log.debug("Doing something");
    return this.somethingDoer.doIt(a, this.someExtraData);
}

另一个在技术上相互递归的例子，但通常只有很少的任何给定函数的激活（中间有几十或数百个其他激活），是通过每个状态具有一个函数并调用它进入该状态来实现的状态机：

void stateA() {
    // do actual work
    // determine which transition applies
    stateB();
}

void stateB() {
    // do actual work
    // determine which transition applies
    state...();
}

// dozens, possibly hundreds of other states
于 2013-08-03T19:25:42.103 回答
1 
int bar(int x);
int foo(int x) { return bar(x); }

foo可以简单的跳转到bar谁直接返回给调用者；任何地方都不需要递归。

于 2013-08-03T18:57:12.277 回答