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) 的结果：Exception in thread "main" java.lang.WhosebugError

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) 可以执行并且 return 结果：fac2(10000) = 284625968091705451890.....

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

Answer 1

这些功能依赖于一个名为 tail recursion, signalled by the tailrec modifier. Tail recursion allows a recursive function to call itself indefinitely without filling up the stack. It relies on the fact that the recursive call (the bit where the function calls itself) is the last call in the method. For more on how and why this works, consider reading some of the 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

因为该函数不是尾递归的，所以它每次递归调用自身时都必须分配一个新的堆栈帧。调用堆栈的大小有限，最终会变满，导致 WhosebugError.

第二个函数通过重写函数解决了这个问题，因此对 fac2 的调用确实是方法中的最后一次调用。这允许它正确使用尾递归，这意味着堆栈不会填满。

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

What's different of these tailrec funtions on kotlin

kotlin

recursion

tail-recursion