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

Question

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

Functions like approximate, which call themselves as their last action, are called tail recursive.

所以，我尝试了这个：

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 DEMO

但它生成以下堆栈跟踪

 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)

这意味着它为每个递归调用生成一个新的堆栈帧。但最后的行动是召唤自己。有什么问题以及如何使其尾递归？

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

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，它会按预期工作。

Answer 2

您的代码工作正常。您在 mc 对象中的价值会随着每一步而减少。在最后一步，您会得到异常。

例如，您可以将函数的 return 类型更改为 Boolean，当您的值为 < 0 时，您可以将其更改为 return false 否则您 return true.

我建议您使用“@tailrec”注解来检查编译器调用的递归函数。

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

Why isn't a function tail recursive?

scala

recursion

tail-recursion