Kotlin中两个tailrec尾递归阶乘函数运行结果不同的原因

核心原因：只有第二个函数符合Kotlin尾递归优化的要求 #

Kotlin的tailrec关键字生效有明确前提：递归调用必须是函数执行的最后一个操作，没有后续运算需要依赖递归调用的返回值。满足该前提时，编译器会直接把递归逻辑转换成等价的循环实现，不会逐层申请函数栈帧，自然不会触发栈溢出。

两个函数的差异分析 #

1. fac1为什么栈溢出

fac1的递归分支逻辑如下：

return n.toBigInteger() * fac1(n-1)

这里最后执行的操作不是fac1(n-1)的递归调用，而是乘法运算：必须等下一层递归返回结果后，才能和当前n的值相乘得到本层的返回值。这种写法完全不满足尾递归要求，即使加了tailrec注解，编译器也无法做优化，本质还是普通递归。调用fac1(10000)时需要连续压入10000层函数栈，超过JVM默认栈深度限制，就会抛出StackOverflowError。

补充：这种不符合尾递归要求的函数加tailrec，IDE会主动抛出警告提示优化无效。

2. fac2为什么可以正常执行

fac2的递归分支逻辑如下：

return if(n == 1L) a else fac2(n -1, a * n.toBigInteger())

它引入了累加器参数a，把本应该在递归返回后执行的乘法，提前放到了递归调用的入参计算阶段完成，递归分支的最后一个操作就是fac2(...)调用本身，没有后续运算依赖递归返回值，完全符合尾递归优化规则。编译器会把这段逻辑直接转换成等价的循环实现：

fun facEquivalent(n: Long): BigInteger {
    var currentN = n
    var accumulator = BigInteger.ONE
    while (currentN != 1L) {
        accumulator *= currentN.toBigInteger()
        currentN -= 1
    }
    return accumulator
}

整个执行过程只会占用1个函数栈帧，不管n是10000还是更大的合法值，都不会出现栈溢出。

内容的提问来源于stack exchange，提问作者Minh Nguyen