Kotlin尾递归函数导致栈溢出

Question

我正在 this easy problem 练习基本的 Kotlin，我运行在递归 return 行上使用以下代码进入堆栈溢出：

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)

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

Kotlin尾递归函数导致栈溢出

Kotlin tail recursive function causing stack overflow

recursion

kotlin

tail-recursion