Intereting Posts
JDK требуется для Kotlin? Kotlin – Характер подачи формы – Незаконный побег: '\ f' Android Studio сообщает «Не удалось определить активность запуска: активность по умолчанию не найдена» при построении проектов Kotlin Интерфейс Azure Mobile App с Android (только для Kotlin) Kotlin более высокий порядок (вызываемые ссылки) компилятор сбой Передача параметров пользовательскому получателю в котлин Как стирается работа в Котлине? упаковать файл Kotlin .class в JAR для выполнения Переопределение нескольких методов интерфейса в лямбда-выражениях Котлина Как узнать, пуст ли массив? Kotlin & Vertx & Mongo: Как управлять функциями async CRUD? Не удалось загрузить ошибку класса kotlin.collections.CollectionsKT при попытке синхронизации градиента Котлин назначает делегата после объявления переменной Как уменьшить размер изображения перед загрузкой, чтобы ускорить приложение? Почему этот Spek на действии не запускается?

tail rec kotlin list

Я пытаюсь сделать некоторые операции, которые приведут к 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 (например, как передавать список как MutableList по параметрам), но, когда это возможно, я стараюсь избегать отправки коллекций, которые нужно изменить внутри функции, и это кажется случайным, что это должно быть возможно.

PS: В вопросительной программе я реализую решение этой проблемы .

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

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

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

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

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

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

Не отказываясь от ответа на вашу головоломку, вот не-хвостовая рекурсивная функция.

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