为什么添加 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 代码会提供正确的结果。当使用调试器运行时，相同的代码会进入无限循环，正如我在心理演练中所期望的那样。这段代码如何在运行时给出正确的结果，但在调试模式下陷入无限循环？

我个人认为正确的实现应该如下所示，但我无法推理为什么第一个是正确的。

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))

Answer 1

b

从

Int.MIN_VALUE

溢出到

Int.Int.MAX_VALUE

，然后到

0

。同时

a

则相反。因为我们需要

2^32 - 3

迭代才能获得从

b

到

-3

的

0

，所以

a

正确地减少了

3

。

我们可以通过使

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

。

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