2014-12-30 122 views
2

我有以下的遞歸函數,我需要轉換爲迭代方案將迭代函數定義爲迭代?

(define (f n) 
    (if (< n 3) n 
    (+ 
     (f (- n 1)) 
     (* 2 (f(- n 2))) 
     (* 3 (f(- n 3))) 
    ) 
    )) 

我的問題是,我在將其轉換爲迭代困難(即做遞歸具有線性執行時間)。我能想到沒有辦法做到這一點,因爲我無法弄清楚如何做到這一點。

的功能定義如下:

f(n) = n if n<3 else f(n-1) + 2f(n-2) + 3f(n-3)

我試圖來計算的話5線,像這樣

1 + 2 + f(3) + f(4) + f(5)

但爲了計算說f(5)我d需要參考f(4), f(3), f(2)f(4)我必須參照f(3), f(2), f(1)

這是SICP書籍中的一個問題。

+0

是的,我們這些誰研究SICP可辨別該來自即時。 ;) – J0e3gan

+0

你有什麼提示嗎? – user50449

回答

1

在書中,作者有一個計算斐波納契數的迭代過程的例子。

(define (fib n) 
    (fib-iter 1 0 n)) 

(define (fib-iter a b count) 
    (if (= count 0) 
    b 
    (fib-iter (+ a b) a (- count 1)))) 

這裏的要點是,使用兩種參數a和b計算期間記憶F(N + 1)和f(n)的。類似的可應用於:我們需要A,B,C記住F(N + 2),F(N + 1)和f(n)的

;; an interative process implementation                              
(define (f-i n)                                    
    ;; f2 is f(n+2), f1 is f(n+1), f0 is f(n)                             
    (define (interative-f f2 f1 f0 count)                              
    (cond                                      
     ((= count 0) f0)                                   
     (else (interative-f                                  
       (+ f2 (* f1 2) (* f0 3))                               
       f2                                     
       f1                                     
       (- count 1)))))                                 
    (interative-f 2 1 0 n))