我在阅读《Joy of Kotlin》一书时遇到了这个有趣的问题。在第4章中,在解释尾递归时,作者提供了一个将两个数字相加的实现,如下所示。
tailrec fun add(a: Int, b: Int): Int = if (b == 0) a else add(inc(a), dec(b))
# where
fun inc(n: Int) = n + 1
fun dec(n: Int) = n - 1
此函数的有趣之处在于 add(3, -3)
返回 0,但如果删除关键字 tailrec
,则会陷入 stackoverflow。当程序看起来不完整时,它如何返回正确的答案。
我反编译了java字节码,看看尾部调用消除是如何完成的,这就是我所看到的。
public static final int add(int a, int b) {
while(b != 0) {
a = inc(a);
b = dec(b);
}
return a;
}
如果我在心里演练代码,循环或之前的递归调用应该会导致无限循环,因为变量 b 永远不会变为零,因为起始值本身是负数。但是,运行上述 kotlin 代码或 java 代码会提供正确的结果。当使用调试器运行时,相同的代码会进入无限循环,正如我在心理演练中所期望的那样。这段代码如何在运行时给出正确的结果,但在 Debug模式下陷入无限循环?
我个人认为正确的实现应该如下,但我无法推理为什么第一个是正确的。
tailrec fun add(a: Int, b: Int): Int =
if (b == 0) a
else if (b > 0) add(inc(a), dec(b))
else add(dec(a), inc(b))
编辑:
@broot 的答案是正确的。使用以下代码验证
tailrec fun add(a: Long, b: Int): Long =
when {
(b == 0) -> a
(b > 0) -> add(inc(a), dec(b))
else -> add(dec(a), inc(b))
}
fun inc(n: Long) = n + 1
fun dec(n: Long): Long = n - 1
fun inc(n: Int) = n + 1
fun dec(n: Int) = n - 1
fun main() {
println(add(3, -4))
println(add(4, -3))
}
最佳答案
b
从 Int.MIN_VALUE
溢出到 Int.MAX_VALUE
,然后转到 0
。同时a
的方向相反。因为我们需要 2^32 - 3
迭代才能将 b
从 -3
变为 0
,a
正确地减少了 3
。另外,由于迭代次数如此之多,如果没有 tailrec
,它就无法工作。
我们可以通过将 a
一侧更改为使用长整型来轻松验证这一点:
tailrec fun add(a: Long, b: Int): Long = if (b == 0) a else add(inc(a), dec(b))
fun inc(n: Long) = n + 1
fun dec(n: Int) = n - 1
在本例中,结果为 4294967296
。
即使它正确地计算了该值,这样使用它也可能不是一个好主意。这几乎是偶然地正常工作。
关于java - 为什么添加 tailrec 会使不正确的 kotlin corecursion 工作?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/76940035/