Kotlin: Endrekursion für beide Seiten rekursiven Funktionen

Question

nehme ich schreiben Code wie folgt:

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

Wie erhalte ich Kotlin diese für beide Seiten rekursiven Funktionen zu optimieren, so dass ich main ohne werfen einen Stackoverflow laufen kann? Das Schlüsselwort tailrec funktioniert für die Rekursion mit einer einzigen Funktion, aber nicht komplizierter. Ich sehe auch eine Warnung, dass keine Tail-Calls gefunden werden, wo das Schlüsselwort tailrec verwendet wird. Vielleicht ist das für Compiler zu schwer?

Answer 1

Was Sie suchen sind „richtige Endrekursion“. Die JVM unterstützt diese nicht, Sie benötigen also trampolines.

Eine richtige Endaufruf reinigt die Erinnerung an seine eigenen Funktion (Parameter, lokale Variablen) vor dem Sprung (statt Aufruf) mit dem Schwanz aufgerufenen Funktion auf. Auf diese Weise kann die Tail-Funktion direkt zu ihrer Caller-Caller-Funktion zurückkehren. Unendliche gegenseitige Rekursion ist möglich. (In funktionalen Sprachen ist dies eine der wichtigsten Funktionen.)

Um richtige Tailaufrufe in Assembler zu ermöglichen, benötigen Sie einen Befehl zum Springen (Goto) zu einer Routine/Methode, auf die über Zeiger verwiesen wird. OOP braucht Anrufe (speichert Speicherort auf dem Stapel zu springen zurück und springt dann) zu einer Routine/Verfahren, die über Zeiger verwiesen wird.

Sie können richtige Tail-Calls mit dem Trampolin-Design-Muster emulieren, vielleicht gibt es Unterstützung über die Bibliothek. Das Trampolin ist eine while-Schleife, die eine Funktion aufruft, die einen Verweis auf die nächste Funktion gibt, die einen Verweis auf den nächsten zurück ...

Answer 2

von Wikipedia https://en.wikipedia.org/wiki/Tail_call:

ein Endrekursion ist ein Unterprogramm-Aufruf als letzte Aktion eines Verfahrens durchgeführt. Wenn ein Endrekursion auf das gleiche Unterprogramm wieder später in der Aufrufkette genannt führen könnte zu sein, wird das Unterprogramm zu dem seinem Schwanz-rekursive

Also Ihr Fall kein Endrekursion definitionsgemäß ist. Das, was die Warnung sagt.

Momentan gibt es keine Möglichkeit, Compiler, dass optimieren, vor allem, weil es eine sehr seltene Situation. Aber ich bin nicht sicher, dass sogar Haskel das weg optimiert.

Answer 3

Hier ist eine Implementierung von @ comonad der trampoline suggestion. Es klappt!

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