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

Question

我正在研究this easy problem以练习基本的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的理解是，将我的递归函数转换为迭代函数是supposed，这不会受到此类崩溃的影响。如果我没有正确实现尾递归，则编译器应该发出错误。

有人可以向我解释为什么这会在大型输入上崩溃，就像标准的递归调用那样吗？

Answer 1

此行为看起来像是短路运算符中的尾调用missing optimization，其中最后一个操作数正在求值的事实意味着表达式结果不再依赖于先前的操作数。

与此同时，您可以将return语句重写为

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

获得相同的结果+尾部调用优化。