Хвостовая рекурсивная функция Kotlin, вызывающая переполнение стека - PullRequest
Новая
       9

Хвостовая рекурсивная функция Kotlin, вызывающая переполнение стека

1 голос
/ 10 ноября 2019

Я работал над этой простой проблемой , чтобы попрактиковаться в базовом 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 состоит в том, что предполагается , чтобы преобразовать мою рекурсивную функцию в итеративную, которая не будет восприимчива к такого рода сбоям. Если бы я не реализовал хвостовую рекурсию правильно, предполагается, что компилятор выдаст ошибку.

Может кто-нибудь объяснить мне, почему это приводит к сбою на больших входах, так же, как это делает стандартный рекурсивный вызов?

1 Ответ

1 голос
/ 10 ноября 2019

Это поведение выглядит как отсутствие оптимизации хвостовых вызовов в короткозамкнутых операторах, где факт, что последний операнд оценивается, означает, что результат выражения больше не зависит от предыдущих операндов.

Между тем, вы можете переписать свой оператор возврата как 

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

, чтобы получить тот же результат + оптимизация хвостового вызова.

...