список хвостов rec kotlin

Я пытаюсь выполнить некоторые операции, которые прямо сейчас могут вызвать StackOverflow в Котлине.

Зная это, я вспомнил, что в 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, но должно ли это иметь значение? Все примеры, которые я вижу в Интернете для хвостового вызова для других языков, допускают такие действия.

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


kotlin functional-programming tail-recursion tail-call-optimization
person Gabryel Monteiro    schedule 13.11.2017    source источник
comment
В принятом ответе на вопрос, который вы связали, конкретно указана версия, где + находится снаружи, в качестве примера функции, которая не является хвостовой рекурсией. Посмотрите на версию с аккумулятором, чтобы увидеть, как выглядит хвостовая рекурсивная версия.   -  person sepp2k    schedule 13.11.2017
comment
@sepp2k sepp2k О, извините, теперь я понял свою ошибку. Странно, как кажется, я уже видел некоторые языки (вероятно, haskell?), которые имели некоторые дополнения к возврату в качестве рекурсии хвостового вызова.   -  person Gabryel Monteiro    schedule 13.11.2017

Ответы (2)


arrow_upward
4
arrow_downward

Ни один из ваших примеров не является хвостовой рекурсией.

Хвостовой вызов — это последний вызов в подпрограмме. Рекурсивный вызов — это вызов подпрограммы самой себе. Хвостовой рекурсивный вызов — это хвостовой вызов подпрограммы самой себе.

Во всех ваших примерах хвостовой вызов относится к +, а не к подпрограмме. Итак, все они являются рекурсивными (потому что они вызывают сами себя), и все они имеют хвостовые вызовы (поскольку у каждой подпрограммы всегда есть «последний вызов»), но ни один из них не является хвостовым рекурсивным (потому что рекурсивный вызов не является последний звонок).

Инфиксная нотация иногда может скрывать, что такое хвостовой вызов, это легче увидеть, когда вы пишете каждую операцию в форме префикса или как вызов метода:

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

Теперь становится намного легче увидеть, что вызов debuffPhase находится не в хвостовой позиции, а скорее это вызов plus (т.е. +), который находится в хвостовой позиции. Если бы в Kotlin были общие хвостовые вызовы, то этот вызов plus действительно был бы устранен, но, насколько мне известно, в Kotlin есть только хвостовая рекурсия (как в Scala), так что этого не будет.

person Jörg W Mittag    schedule 13.11.2017
comment
Хорошее объяснение, теперь оно имеет для меня гораздо больше смысла. Я просто немного запутался, потому что я думаю, что уже видел функции на каком-то языке, рассматривающие дополнения при возврате как хвостовые вызовы. Но я тоже могу ошибаться, так как я впервые использую рекурсию хвостового вызова. - person Gabryel Monteiro; 13.11.2017
comment
Я думаю, что уже видел функции на каком-то языке, рассматривающие дополнения при возврате как хвостовые вызовы. – Да, дополнения являются хвостовыми звонками, именно в этом проблема! Хвостовой вызов относится к +, рекурсивный вызов — к debuffPhase, следовательно, debuffPhase является рекурсивным (поскольку он вызывает сам себя), но не хвостовым рекурсивным (поскольку он не вызывает сам себя). - person Jörg W Mittag; 13.11.2017

arrow_upward
0
arrow_downward

Не давая ответа на вашу загадку, вот функция, не являющаяся хвостовой рекурсией.

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

Это не хвостовая рекурсия, потому что рекурсивный вызов не находится в хвостовой позиции, как отмечено в ответе Йорга.

Его можно преобразовать в хвостовую рекурсивную функцию с помощью 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)
}
person ephemient    schedule 13.11.2017
comment
О, спасибо, я не знал этой техники CPS, она мне очень помогла преобразовать мои ответы. Хотя кажется, что я где-то допустил ошибку при преобразовании, сейчас это ближе, чем раньше, к настоящей функции хвостового вызова. - person Gabryel Monteiro; 13.11.2017
comment
Это не CPS, если вы посмотрите на определение. Это будет fun <T> fac2(n: Int, k: Int => T), и вам нужны версии CPS <=, -1 и *. - person Alexey Romanov; 13.11.2017
comment
@AlexeyRomanov Хорошо, да, моя терминология неверна. Это просто использование аккумулятора. Правильное преобразование CPS будет выглядеть как fun fac2(n: Int, k: (Int) -> Int = { it }): Int = if (n <= 1) k(1) else fac2(n - 1) { k(n * it) }. - person ephemient; 13.11.2017