Kotlin：相互再帰関数のための末尾再帰

Question

私はこのようなコードを書くとします

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

私はにStackOverflowErrorをスローせずにmainを実行できるように、私は、Kotlinは、これらの相互再帰関数を最適化するために得る方法を教えてください。 tailrecキーワードは、単一機能の再帰で機能しますが、それ以上の複雑さはありません。また、tailrecキーワードが使用されている場合、テールコールが見つからないという警告も表示されます。おそらくこれはコンパイラにとっては難しいでしょうか？ウィキペディアhttps://en.wikipedia.org/wiki/Tail_callことで

Answer 1

あなたが探しているのは「適切なテールコール」です。 JVMはそれらをサポートしていないので、trampolinesが必要です。

適切なテールコールは、functionというテールに（呼び出しの代わりに）ジャンプする前に、独自の関数（パラメータ、ローカル変数）のメモリをクリーンアップします。こうすることで、functionという尾部が直接呼び出し元関数に戻ることができます。無限相互再帰が可能です。

アセンブラで適切なテールコールができるようにするには、ポインタを介して参照されるルーチン/メソッドにジャンプするコマンドが必要になります（これは、機能的な言語では最も重要な機能の1つです）。 OOPは、ポインタを介して参照されるルーチン/メソッドにコール（スタック上にジャンプしてからジャンプする場所）を必要とします。

トランポリンのデザインパターンで適切なテールコールをエミュレートすることができます。おそらくライブラリ経由でいくつかのサポートがあります。 トランポリンは、次の関数への参照を返す関数を呼び出すwhileループです。

Answer 2

：

テール呼び出しは、手続きの最終アクションとして実行されるサブルーチン・コールです。もしテールコールが同じサブルーチンをコールチェーンの後で呼び出されるようにした場合、サブルーチンは末尾再帰と呼ばれます。

したがって、あなたのケースはテール再帰ではありません。それは警告が言うことではありません。

現在、非常にまれな状況であるため、コンパイラが最適化する方法はありません。 しかし、私はハスケルでさえそれを最適化することは確実ではない。

Answer 3

ここに@comonadのtrampoline suggestionの実装があります。できます！

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