Котлин: Рекурсия хвоста для взаимно-рекурсивных функций

Предположим, что я пишу код следующим образом:

tailrec fun odd(n: Int): Boolean = if (n == 0) false else even(n - 1) tailrec fun even(n: Int): Boolean = if (n == 0) true else odd(n - 1) fun main(args:Array<String>) { // :( java.lang.StackOverflowError System.out.println(even(99999)) } 

Как заставить Kotlin оптимизировать эти взаимно рекурсивные функции, чтобы я мог запускать main не бросая StackOverflowError? tailrec слово tailrec работает для рекурсии с одной функцией, но ничего сложнее. Я также вижу предупреждение о том, что хвостовые вызовы не найдены, где tailrec ключевое слово tailrec . Возможно, это слишком сложно для компиляторов?

    То, что вы ищете, это «правильные хвостовые звонки». JVM не поддерживает их, поэтому вам нужны батуты .

    Правильный хвостовой вызов очищает память своей собственной функции (параметры, локальные переменные) перед тем, как прыгать (вместо вызова) в функцию, называемую хвостом. Таким образом, функция, называемая хвостом, может вернуться непосредственно к ее вызывающей функции-вызывающему. Возможна бесконечная взаимная рекурсия. (В функциональных языках это одна из самых важных функций.)

    Чтобы разрешить правильные хвостовые вызовы в ассемблере, вам понадобится команда для перехода (goto) к подпрограмме / методу, на который ссылается через указатель. ООП нуждается в вызовах (местоположение магазинов, чтобы вернуться в стек, а затем переходить) к процедуре / методу, на который ссылается через указатель.

    Вы можете эмулировать правильные хвостовые звонки с шаблоном проектирования батута, возможно, есть некоторая поддержка через библиотеку. Батут – это цикл while, который вызывает функцию, которая возвращает ссылку на следующую функцию, которая возвращает ссылку на следующую …

    По wikipedia https://en.wikipedia.org/wiki/Tail_call :

    хвостовой вызов – вызов подпрограммы, выполняемый как окончательное действие процедуры. Если вызов хвоста может привести к тому, что одна и та же подпрограмма будет вызвана позже в цепочке вызовов, подпрограмма называется хвостовой рекурсивной

    Таким образом, ваш случай не является хвостовой рекурсией по определению. Вот что предупреждает.

    В настоящее время компилятор не может оптимизировать это, главным образом потому, что это очень редкая ситуация. Но я не уверен, что даже Haskel оптимизирует это.

    Вот реализация батут-предложения @ comonad. Оно работает!

     import kotlin.reflect.KFunction typealias Result = Pair<KFunction<*>?, Any?> typealias Func = KFunction<Result> tailrec fun trampoline(f: Func, arg: Any?): Any? { val (f2,arg2) = f.call(arg) @Suppress("UNCHECKED_CAST") return if (f2 == null) arg2 else trampoline(f2 as Func, arg2) } fun odd(n: Int): Result = if (n == 0) null to false else ::even to n-1 fun even(n: Int): Result = if (n == 0) null to true else ::odd to n-1 fun main(args:Array<String>) { System.out.println(trampoline(::even, 9999999)) }