2016-03-01 107 views
7

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

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

+0

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

+1

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

回答

2

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

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

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

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

+1

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

3

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

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

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

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

+4

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

+0

它呢?涼!我認爲是這樣,只是因爲它是Haskell,它會的。謝謝你的提示。 – voddan

+0

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

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

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