java - 为什么添加 tailrec 会使不正确的 kotlin corecursion 工作？

Question

我在阅读《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))
}

Answer 1

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。

即使它正确地计算了该值，这样使用它也可能不是一个好主意。这几乎是偶然地正常工作。