Kotlin tail recursive function causing stack overflow

Question

I was working on this easy problem to practice basic Kotlin, and I ran into a stack overflow with the following code on the recursive return line:

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)
    }
}

My understanding of tailrec is that it's supposed to convert my recursive function into an iterative one, which wouldn't be susceptible to this sort of crash. If I didn't implement tail recursion correctly, the compiler is supposed to issue an error.

Can someone explain to me why this crashes on large inputs, just like a standard recursive call would?

Ah, and leetcode is suppressing warnings, and writing a tailrec function that isn't tail recursive only generates a warning, not an error. — EntangledLoops
– EntangledLoops, Commented Nov 10, 2019 at 3:08
I'm still curious were the difference is between the if(...) ... else tailCall() example in the docs and the ... && tailCall() in your example. As far as I can see there is no difference. — Jonas Wilms
– Jonas Wilms, Commented Nov 10, 2019 at 3:10

Ilya · Accepted Answer · 2019-11-10 03:30:02Z

3

This behavior looks like a missing optimization of tail calls in short circuiting operators, where the fact that the last operand is being evaluated means that the expression result doesn't depend anymore on the previous operands.

Meanwhile you can rewrite your return statement as

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

to get the same result + tail call optimization.

edited Nov 10, 2019 at 3:30

answered Nov 10, 2019 at 3:15

Ilya

23.3k9 gold badges79 silver badges96 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Kotlin tail recursive function causing stack overflow

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related