Tail recursion in linked list


#1

I had a problem yesterday with a linked data-structure that looked like this:

class ItemRow(private val nextRow: ItemRow?) {
    
    fun pushOverflow(width) {
        // work on this row

        nextRow?.pushOverflow(width)
    }
}

The last line quickly lead to a stack-overflow. I solved it by calling the method from outside, but is there a way to mark this function as tail-recursive?


#2

Have you tried to use tailrec as explained here https://kotlinlang.org/docs/reference/functions.html#tail-recursive-functions ? Does it work for you?


#3

Yes, it tells me that tailrec can’t be applied since the method isn’t calling itself, but the same method on the next object in the chain.


#4

You are right. It is not supported yet. There is a CR about that: https://youtrack.jetbrains.com/issue/KT-15341


#5

Is there a way to use an extension method instead? That would essentially be a single function, so it could be made tail recursive. It doesn’t allow you to use inheritance, but it doesn’t look like you are anyway.


#6

I guess you can write it like this:

class ItemRow(var nextRow: ItemRow?)

tailrec fun ItemRow.pushOverflow(width: Int) {
    nextRow?.pushOverflow(width)
}