为什么一个函数不是尾递归的？

Question

我正在阅读 M. Odersky 的《Scala 编程》一书，他说：

像 approximate 这样在最后调用自己的函数被称为尾递归。

于是，我尝试了这个例子：

object Main extends App {
    implicit val mc = new MyClass(8)
    val ti = new TestImplct
    ti.test
}

class TestImplct {
  def test(implicit mc : MyClass): Unit = {
    println(mc.i)
    mc.i -= 1
    if(mc.i < 0){
      throw new IllegalArgumentException
    }
    test
  }
}

class MyClass(var i : Int)

IDEONE演示

但它生成了以下堆栈跟踪信息

 Exception in thread "main" java.lang.IllegalArgumentException
    at TestImplct.test(Main.scala:13)
    at TestImplct.test(Main.scala:15)
    at TestImplct.test(Main.scala:15)
    at TestImplct.test(Main.scala:15)
    at TestImplct.test(Main.scala:15)
    at TestImplct.test(Main.scala:15)
    at TestImplct.test(Main.scala:15)
    at TestImplct.test(Main.scala:15)
    at TestImplct.test(Main.scala:15)

这意味着每次递归调用都会生成一个新的堆栈帧。但最后一步是对自身的调用。有什么问题，如何使其成为尾递归？

为什么编译器不进行尾调用优化？

- stella

---

你的作用域中是否有 MyClass 的隐式实例？ - Samar

@Samar 是的，我有。看一下演示。 - stella

我看到你定义了这个类，但是我没有看到你在哪里实例化它。 - Samar

@Samar Ah，你说得对。我没有附上完整的代码。抱歉。 - stella

它运行得很好。你为什么认为它不是尾递归？它只是因为if条件而退出。 - Samar

@Samar 我认为是这样，因为编译器不执行尾调用优化。 - stella

Answer 1

您可以尝试使用@tailrec注释标记该方法。如果这样做，编译将失败，并显示为什么编译器无法将其优化为尾递归的原因：

Main.scala:12: error: could not optimize @tailrec annotated method test: it is neither private nor final so can be overridden

实际上，如果将该方法设置为final，则它将按预期工作。

- Tzach Zohar

---

有趣。为什么将该方法设为final可以在这里允许TCO？ - Samar

@Samar + 1，还想知道。 - stella

正如错误所说：否则方法可能被某些非尾递归的实现覆盖，那么您可能会认为自己正在查看尾递归，而实际上并非所有调用都能进行此优化。 - Tzach Zohar

Answer 2

你的代码可以正常运行。在每一步中，mc对象中的值会减少。在最后一步，你会得到一个异常。

你可以将函数的返回类型更改为Boolean，例如当值为<0时返回false，否则返回true。

我建议你使用'@tailrec'注释，以便编译器检查递归函数调用。

- codejitsu