尾部 rec kotlin 列表

Question

我正在尝试执行一些会在 Kotlin 中导致 Whosebug 的操作。

知道了，我想起Kotlin是支持tailrec函数的，所以我试着做了：

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

令我惊讶的是 IDEA 没有将其识别为 tailrec，我试图将其取消扩展功能并使其成为普通功能：

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

即便如此，也不被接受。重要的不是最后一个函数调用是同一个函数吗？我知道 + 是 List plus 函数的标志，但它应该有所作为吗？我在互联网上看到的所有其他语言的尾调用示例都允许 actions.

我也尝试用 Int 来做到这一点，这似乎比添加到列表更常用，但结果相同：

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

不是所有这些实现都应该允许尾调用吗？我想到了其他一些方法来解决这个问题（比如也将列表作为 MutableList 传递给参数），但在可能的情况下，我尽量避免发送要在函数内部更改的集合，这似乎是应该的情况有可能。

PS: 关于题目程序，我正在实现这个problem的解决方案。

Answer 1

None 你的例子是尾递归的。

尾调用是子例程中的最后一次调用。递归调用是子程序对其自身的调用。尾递归调用是子例程对其自身的尾调用。

在您的所有示例中，尾调用是针对 +，而不是针对子例程。所以，所有这些都是递归的（因为它们调用自己），并且所有这些都有尾调用（因为每个子例程总是有一个 "last call"），但是它们中的 none 是尾递归的（因为递归调用不是最后一次调用）。

中缀符号有时会模糊尾调用是什么，当您以前缀形式或方法调用编写每个操作时更容易看到：

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

现在更容易看出对 debuffPhase 的调用不在尾部位置，而是对 plus（即 +）的调用在尾部位置。如果 Kotlin 有一般的尾调用，那么 that 对 plus 的调用确实会被消除，但是 AFAIK，Kotlin 只有尾递归（像 Scala），所以它不会.

Answer 2

在不给出您的谜题答案的情况下，这是一个非尾递归函数。

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

它不是尾递归，因为递归调用不在尾部位置，如 Jörg 的回答所述。

可以使用CPS,

转化为尾递归函数

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

尽管更好的界面可能会将延续隐藏在私有辅助函数中。

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

尾部 rec kotlin 列表

tail rec kotlin list

functional-programming

tail-recursion

tail-call-optimization

kotlin