面试题：Kotlin尾递归优化的基本条件

Question

在Kotlin中，实现尾递归优化需要满足哪些基本条件？请举例说明一个简单的尾递归函数，并阐述如何使其满足尾递归优化条件。

Answer 1

1. 尾递归优化基本条件：
   • 函数的递归调用必须是函数体的最后一个操作，即递归调用之后不能再有其他计算或操作。
   • 递归调用的返回值必须直接作为整个函数的返回值。
2. 简单尾递归函数示例及优化：
   • 未优化的递归函数示例：

fun factorial(n: Int): Int {
    if (n <= 1) {
        return 1
    }
    return n * factorial(n - 1)
}

在这个函数中，factorial(n - 1)不是函数体的最后一个操作，因为还要乘以n，所以它不是尾递归，当n较大时容易导致栈溢出。

• 优化为尾递归函数：

tailrec fun factorialHelper(n: Int, acc: Int = 1): Int {
    if (n <= 1) {
        return acc
    }
    return factorialHelper(n - 1, acc * n)
}
fun factorial(n: Int): Int = factorialHelper(n)

在factorialHelper函数中，factorialHelper(n - 1, acc * n)是函数体的最后一个操作，并且它的返回值直接作为整个函数的返回值，满足尾递归优化条件。通过引入一个累加器acc，将乘法操作放在递归调用的参数中，从而实现尾递归优化，避免栈溢出问题。