科特林：尾遞歸的相互遞歸函數

假設我寫這樣的代碼：科特林：尾遞歸的相互遞歸函數

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？ tailrec關鍵字適用於單一函數遞歸，但沒有更復雜的內容。我還看到一個警告，即在使用tailrec關鍵字的地方找不到尾部呼叫。對於編譯器來說這可能太難了？

來源

2016-03-01 denine99

您可以將功能請求添加到https://youtrack.jetbrains.com以獲得「互尾遞歸」功能，如果您希望將它添加到Kotlin中，那麼這是最好的選擇。如果它已經被請求或計劃，那麼還要首先在那裏搜索。 –

我在這裏創建了一個Kotlin問題：https://youtrack.jetbrains.com/issue/KT-11307 – denine99

你在找什麼是「正確的尾巴呼叫」。 JVM不支持這些，所以你需要trampolines。

正確的尾部調用在跳躍（而不是調用）到尾部調用函數之前清除其自身函數（參數，局部變量）的內存。這樣，尾部調用函數可以直接返回其調用者函數。無限的相互遞歸是可能的。（在功能語言中，這是最重要的功能之一）。

爲了在彙編程序中允許正確的尾調用，您需要一個命令來跳轉（轉到）通過指針引用的例程/方法。 OOP需要調用（存儲位置跳轉到堆棧然後跳轉）到通過指針引用的例程/方法。

你可以用蹦牀設計模式模擬正確的尾巴調用，也許有一些通過庫的支持。蹦牀是一個while循環，它調用一個函數，它返回對下一個函數的引用，它返回對下一個函數的引用...

來源

2017-06-19 08:54:54 comonad

很酷，聽起來我們可以通過編寫一個蹦牀方法來支持JVM中的這個方法，該方法使用給定的參數調用方法引用。應該修改'even'和'odd'函數以返回方法引用加上下一個參數。我們通過調用trampoline方法並引用'even'函數和參數'99999'來進行第一次調用。 – denine99

維基百科https://en.wikipedia.org/wiki/Tail_call：

尾部呼叫是作爲一個程序的最後動作進行子程序調用。如果尾調用可能會導致相同的子程序被再次調用鏈後來被稱爲，子程序據說是尾遞歸

所以你的情況不會被定義爲一個尾遞歸。這不是警告所說的。

目前沒有辦法編譯器會優化，主要是因爲這是非常罕見的情況。 ~~但我不確定連Haskel都會優化這一點。~~

來源

2016-03-01 05:58:33 voddan

在同一頁（稍作編輯）：「功能性語言[如Kotlin]，目標是JVM [傾向於]實現直接[或自我]尾遞歸，但不是相互尾尾遞歸。「我可以向你保證，Haskell支持相互尾部遞歸。 –

它呢？涼！我認爲是這樣，只是因爲它是Haskell，它會的。謝謝你的提示。 – voddan

你能否進一步澄清？在偶數/奇數的例子中，even和off的最終動作是一個子程序調用，我們看到在調用鏈中稍後調用相同的子程序。因此，通過定義，這兩個函數都是尾遞歸的。 – denine99

這是@ 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)) 
}

來源

2017-06-22 09:12:06 denine99

酷！ :)有沒有辦法通過Runnable來做到這一點？ – comonad

科特林：尾遞歸的相互遞歸函數

回答

相關問題