除了尾递归，什么是尾调用优化？

Question

除了尾递归之外，是否还有其他的尾调用优化方法？我一直在尝试寻找或思考不涉及递归的方法，但没有成功。这是否可能？有没有例子？

- dtech

---

“Continuations”（http://en.wikipedia.org/wiki/Continuation-passing_style）可能符合尾调用优化的条件。 - stakx - no longer contributing

Answer 1

当然，“尾调用优化”实际上是这种优化最普遍、与递归无关的术语。这种优化并不会将递归替换为类似于while循环的等效操作。相反，尾调用会被转换以重用调用者的栈帧。任何形式为“return f(...)”或“f(...); return”的代码都适用于此优化。它适用于任何f，甚至适用于函数指针/闭包/虚拟方法，编译器可能无法知道正在调用什么。因此，它也更适用于分离编译、高阶函数、后期绑定等。

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

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

- user395760

Answer 2

int bar(int x);
int foo(int x) { return bar(x); }

foo 可以直接跳转到返回给调用者的 bar，无需在任何地方进行递归。

- user541686

---

@ddriver：我刚刚删除了bar的定义，只留下了它的声明。你不能在没有定义的情况下将bar内联，但是你可以对调用者执行尾递归优化。看到区别了吗？ - user541686

这实际上是一对潜在的相互递归函数中的一半... - user529758

@H2CO3：啥？尾调用优化不在乎这些是否相互递归... - user541686

@Mehrdad 我知道，这不是我的重点...只是纠结于细节。OP想要一个没有递归的东西。 - user529758