2010-09-17 119 views
1

可能重複:
Combine memoization and tail-recursionMemoizing尾調用優化遞歸函數

所以下面是代碼我寫,尾調用使用可變累積優化

let rec counter init count = 
    if init = 1 then count + 1 else 
    match init with 
    | Even value -> (counter (value/2) (1 + count)) 
    | Odd value -> (counter ((3 * value) + 1) (count+1)) 

let SeqBuilder (initval:int) : int = 
    counter initval 0 

我該如何記憶?當我試圖記憶它時遇到的問題是,遞歸調用必須去memoize對象,所以你必須有一個...遞歸對象?

還是更簡單一些,我只是缺乏經驗?

回答

3

F#允許您定義一個遞歸值(像你提到的遞歸對象),所以如果你有memoize2功能做記憶化(取的兩個參數的函數 - 使其與您counter兼容),那麼你可以寫:

let rec counter = memoize2 (fun init count -> 
    if init = 1 then count + 1 else 
    match init with 
    | Even value -> (counter (value/2) (1 + count)) 
    | Odd value -> (counter ((3 * value) + 1) (count+1))) 

像這樣的遞歸引用可能是危險的,所以F#插入一些運行時檢查。它也給出了一個警告FS0040來通知你這件事,但在這種情況下,遞歸是正確的(如果遞歸引用在初始化過程中被訪問過,則會發生問題 - 這裏我們稍後使用它,當函數已經被聲明時,很好)。您可以通過添加#nowarn "40"來禁用該警告。

+0

現在你的計數器不是尾遞歸 – 2010-09-18 05:19:09