tail rec kotlin list

Question

I'm trying to do some operations that would cause a StackOverflow in Kotlin just now.

Knowing that, I remembered that Kotlin has support for tailrec functions, so I tried to do:

private tailrec fun Turn.debuffPhase(): List<Turn> {
    val turns = listOf(this)
    if (facts.debuff == 0 || knight.damage == 0) {
        return turns
    }

    // Recursively find all possible thresholds of debuffing
    return turns + debuff(debuffsForNextThreshold()).debuffPhase()
}

Upon my surprise that IDEA didn't recognize it as a tailrec, I tried to unmake it a extension function and make it a normal function:

private tailrec fun debuffPhase(turn: Turn): List<Turn> {
    val turns = listOf(turn)
    if (turn.facts.debuff == 0 || turn.knight.damage == 0) {
        return turns
    }

    // Recursively find all possible thresholds of debuffing
    val newTurn = turn.debuff(turn.debuffsForNextThreshold())
    return turns + debuffPhase(newTurn)
}

Even so it isn't accepted. The important isn't that the last function call is to the same function? I know that the + is a sign to the List plus function, but should it make a difference? All the examples I see on the internet for tail call for another languages allow those kind of actions.

I tried to do that with Int too, that seemed to be something more commonly used than addition to lists, but had the same result:

private tailrec fun discoverBuffsNeeded(dragon: RPGChar): Int {
    val buffedDragon = dragon.buff(buff)
    if (dragon.turnsToKill(initKnight) < 1 + buffedDragon.turnsToKill(initKnight)) {
        return 0
    }

    return 1 + discoverBuffsNeeded(buffedDragon)
}

Shouldn't all those implementations allow for tail call? I thought of some other ways to solve that(Like passing the list as a MutableList on the parameters too), but when possible I try to avoid sending collections to be changed inside the function and this seems a case that this should be possible.

PS: About the question program, I'm implementing a solution to this problem.

The accepted answer to the question you linked specifically lists the version where the + is outside as an example of a function that isn't tail recursive. Look at the version with the accumulator to see what a tail recursive version looks like. — sepp2k, Nov 13 '17 at 02:12
@sepp2k Oh, sorry, I understood now my error. Strange, as it seems I alreasy saw some languages(probably haskell?) that had some addition on a return as tail call recusrions. — Gabryel Monteiro, Nov 13 '17 at 04:38

Jörg W Mittag · Accepted Answer · 2017-11-13T01:41:57.300

None of your examples are tail-recursive.

A tail call is the last call in a subroutine. A recursive call is a call of a subroutine to itself. A tail-recursive call is a tail call of a subroutine to itself.

In all of your examples, the tail call is to +, not to the subroutine. So, all of those are recursive (because they call themselves), and all of those have tail calls (because every subroutine always has a "last call"), but none of them is tail-recursive (because the recursive call isn't the last call).

Infix notation can sometimes obscure what the tail call is, it is easier to see when you write every operation in prefix form or as a method call:

return plus(turns, debuff(debuffsForNextThreshold()).debuffPhase())
// or
return turns.plus(debuff(debuffsForNextThreshold()).debuffPhase())

Now it becomes much easier to see that the call to debuffPhase is not in tail position, but rather it is the call to plus (i.e. +) which is in tail position. If Kotlin had general tail calls, then that call to plus would indeed be eliminated, but AFAIK, Kotlin only has tail-recursion (like Scala), so it won't.

Good explanation, now it makes a lot more sense to me. I just am a little confused, because I think I already saw functions on some language considering additions on return as tail calls. But I can be wrong too, as it is my first time using tail-call recursion. — Gabryel Monteiro, Nov 13 '17 at 04:44
"I think I already saw functions on some language considering additions on return as tail calls." – Yes, the additions *are* the tail calls, that's precisely the problem! The tail call is to `+`, the recursive call is to `debuffPhase`, ergo, `debuffPhase` is recursive (because it calls itself), but not tail-recursive (because it doesn't tail call itself). — Jörg W Mittag, Nov 13 '17 at 08:46

score 1 · Answer 2 · answered Nov 13 '17 at 01:50

1

Without giving away an answer to your puzzle, here's a non-tail-recursive function.

fun fac(n: Int): Int =
    if (n <= 1) 1 else n * fac(n - 1)

It is not tail recursive because the recursive call is not in a tail position, as noted by Jörg's answer.

It can be transformed into a tail-recursive function using CPS,

tailrec fun fac2(n: Int, k: Int = 1): Int =
    if (n <= 1) k else fac2(n - 1, n * k)

although a better interface would likely hide the continuation in a private helper function.

fun fac3(n: Int): Int {
    tailrec fun fac_continue(n: Int, k: Int): Int =
        if (n <= 1) k else fac_continue(n - 1, n * k)
    return fac_continue(n, 1)
}

answered Nov 13 '17 at 01:50

ephemient

198,619
38
280
391

Oh, thank you, I didn't know this CPS technique, it did help me quite a bit converting my answers. Although it seems I committed an error on conversion somewhere, it is closer now than before to being a true tail call function. – Gabryel Monteiro Nov 13 '17 at 04:36
That's not CPS, if you look at the definition. That would be `fun fac2(n: Int, k: Int => T)`, and you need CPS versions of `<=`, `-1` and `*`. – Alexey Romanov Nov 13 '17 at 09:32
@AlexeyRomanov Ok yes, my terminology is wrong. This is just using an accumulator. A proper CPS transform would look like `fun fac2(n: Int, k: (Int) -> Int = { it }): Int = if (n <= 1) k(1) else fac2(n - 1) { k(n * it) }`. – ephemient Nov 13 '17 at 09:44

tail rec kotlin list

2 Answers2