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

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

见SICP中的练习1.30。比尔有个解决办法。

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