kotlin - kotlin 中这些 tailrec 函数有什么不同

Question

我正在 Kotlin 中练习递归，并在运行以下 2 个函数时得到了其他结果:

tailrec fun fac1(n: Long): BigInteger {
    if(n == 1L)
        return BigInteger.ONE
    else
        return n.toBigInteger() * fac1(n-1)
}
println("fac1(10000) = ${fac1(10000)}")

fac1(10000)的结果:线程“main”中出现异常java.lang.StackOverflowError

tailrec fun fac2(n: Long, a: BigInteger = BigInteger.ONE): BigInteger {
    return if(n == 1L) a else fac2(n -1, a * n.toBigInteger())
}
println("fac2(10000) = ${fac2(10000)}")

fac2(10000) 可以执行并返回结果:fac2(10000) = 284625968091705451890.....

有人可以向我解释一下这两个函数之间的区别以及为什么函数 2 可以执行而函数 1 不能执行吗？

Answer 1

这些函数依赖于一个名为 tail recursion 的概念。 ，由 tailrec 修饰符发出信号。尾递归允许递归函数无限期地调用自身，而不会填满堆栈。它依赖于这样一个事实:递归调用(函数调用自身的位)是方法中的最后一次调用。有关其工作方式和原因的更多信息，请考虑阅读 Wikipedia entry on tail calls 中的一些内容。以下是一小段摘录:

When a function is called, the computer must "remember" the place it was called from [...] so that it can return to that location [...] once the call is complete. Typically, this information is saved on the call stack [...]. For tail calls, there is no need to remember the caller – instead, tail call elimination makes only the minimum necessary changes to the stack frame before passing it on, and the tail-called function will return directly to the original caller.

您的第一个函数的问题在于它并不是真正的尾递归。对于尾递归的函数来说，调用自身必须是它所做的最后一件事。

但是要执行n.toBigInteger() * fac1(n-1)行，您首先必须执行fac1(n-1)，并且然后将其乘以n.toBigInteger()。这意味着该函数执行的最后一件事是乘法，而不是调用 fac1。

当您编译此代码时，编译器应该警告您 tailrec 修饰符在这里无效。我的编译器给了我这个警告:

A function is marked as tail-recursive but no tail calls are found

由于该函数不是尾递归的，因此每次递归调用自身时，它都必须分配一个新的堆栈帧。调用堆栈的大小有限，最终会变满，从而导致 StackOverflowError。

第二个函数通过重写函数来解决这个问题，以便对 fac2 的调用实际上是方法中的最后一次调用。这使得它能够正确使用尾递归，这意味着堆栈不会填满。