如何編寫迭代版本的遞歸方案代碼

Question

(define (g-sum f a b) 
    (if (= a b) 
     (f b) 
     (+ (f b) (g-sum f a (- b 1))))) 

我不知道如何改變這個，所以它可以迭代。

Answer 1

你可以試試這個：

(define (g-sum f a b) 
    (let loop ((acc 0) (b b)) 
    (if (< b a) 
     acc 
     (loop (+ (f b) acc) (- b 1))))) 

轉化遞歸過程變成一個迭代過程的竅門是通過周圍的累積結果的參數和的最後返回它遞歸，確保遞歸調用是我們在遞歸步驟中做的最後一件事情，不需要計算。

爲了簡單起見，我使用了一個名爲let，但這不是必需的，因爲使用輔助內部過程會產生同樣的效果。上面的代碼是相同的：

(define (g-sum f a b) 
    (define (loop acc b) 
    (if (< b a) 
     acc 
     (loop (+ (f b) acc) (- b 1)))) 
    (loop 0 b)) 

如果您仍然有問題抓上面的代碼，切記內助過程可以，只要我們沿着所需的參數傳遞提取出來作爲一個單獨的程序。關鍵是，你需要需要一個額外的參數來作爲累加器，你怎麼做這是無關緊要的，我個人更喜歡使用一個名爲let。這相當於我以前的兩種解決方案：

(define (g-sum f a b) 
    (loop f a b 0)) 

(define (loop f a b acc) 
    (if (< b a) 
     acc 
     (loop f a (- b 1) (+ (f b) acc)))) 

Answer 2

參見練習1.30在SICP。 Bill在這裏有一個解決方案。

http://www.billthelizard.com/2010/04/sicp-exercise-130-iterative-sums.html