如何優化遞歸函數

的斯卡拉雙呼叫我試圖讓這個遞歸函數的工作：如何優化遞歸函數

@tailrec 
def rec(n: BigInt): BigInt = { 
    if (n == 0) 0 
    else if (n == 1) 1 
    else (rec(n - 1) + rec(n - 2)) 
}

Error:(13, 24) could not optimize @tailrec annotated method rec: it contains a recursive call not in tail position else (rec(n - 1) + rec(n - 2))

這可怎麼優化，tailrec工作？

來源

2017-03-10 Heer

你將不得不寫一個尾遞歸輔助函數：

def rec(n: BigInt): BigInt = { 
    @tailrec 
    def helper(n: BigInt, previous: BigInt, next: BigInt): BigInt = { 
    if (n == 0) previous 
    else if (n == 1) next 
    else helper(n - 1, next, (next + previous)) 
    } 
    helper(n,0,1) 
}

這一點，所以你可以通過你的序列的過去和未來值的功能，從而使你只拿到一個電話給你的功能。

這是一種常見模式，因爲許多遞歸算法只能通過附加控制流機制（例如：continuation passing）進行尾遞歸。因子是另一個很好的例子，需要用一個額外的參數編寫一個輔助函數來使其尾遞歸。

來源

2017-03-10 11:03:08

讓我補充一點，一般來說，尾遞歸（helper）方法將總是如下所示：def helper（r：Result，w：Work）其中Result和Work類型被選中以適合您的問題。在這種情況下，Result是BigInt，Work是（BigInt，BigInt）。顯然，你可以像盧卡那樣重新開展工作，但它並沒有改變基本的想法。如果你有一個快速返回的條件或者其他一些特殊的處理過程，它可能會變得更復雜一些，但通常它看起來像這樣。 – Phasmid

如何優化遞歸函數

回答

相關問題