导致堆栈溢出的Kotlin尾部递归函数

Question

我正在研究这个简单的问题来练习基本Kotlin，在递归返回行上遇到了堆栈溢出，代码如下：

class Solution {
    fun isPalindrome(s: String): Boolean {
        val cleaned = s.toLowerCase().replace(Regex("[^a-z0-9]"), "")
        tailrec fun isPalindrome(start: Int, end: Int): Boolean {
            if (start >= end) return true
            return cleaned[start] == cleaned[end] && isPalindrome(start+1, end-1)
        }
        return isPalindrome(0, cleaned.length-1)
    }
}

我对tailrec的理解是，它应该将递归函数转换为迭代函数，而迭代函数不会受到这种崩溃的影响。如果我没有正确实现尾部递归，编译器应该会发出错误。

有人能解释一下为什么这会像标准递归调用一样在大输入上崩溃吗？

Answer 1

这种行为看起来像是短路运算符中尾部调用的缺失优化，其中正在计算最后一个操作数的事实意味着表达式结果不再依赖于之前的操作数。

同时，您可以将返回语句重写为

return if (cleaned[start] != cleaned[end]) false else isPalindrome(start+1, end-1)

为了得到相同的结果，尾部调用优化。