如何编写迭代版本的递归方案代码

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