SICP 递归过程与迭代过程：使用递归过程生成迭代过程

Question

在SICP中第1.2.1节作者在下面给出了这样一个代码示例来展示如何使用迭代过程来解决阶乘问题：

(define (factorial n)
  (fact-iter 1 1 n))
(define (fact-iter product counter max-count)
  (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (+ counter 1)
                 max-count)))

并说 “我们将诸如fact-iter之类的递归过程称为生成迭代过程，这似乎令人不安。但是，该过程确实是迭代的：它的状态完全由其三个状态变量捕获，并且解释器需要保留仅跟踪三个变量即可执行该过程。”

我不明白作者的意思。递归过程和递归过程有什么区别？而他为什么说下面的递归过程生成迭代过程呢？

Answer 1

“递归过程”需要在递归调用进行时维护调用者的状态。例如，如果您写道：

(define (fact-recurse n)
  (if (< n 2)
      1
      (* n (fact-recurse (- n 1)))))

外部调用必须记住

n

并等待内部调用返回才能执行乘法。如果您调用

(fact-recurse 10)

，当函数到达其递归末尾时，将会有 9 个堆叠乘法待处理。但是在

迭代过程

中，早期的状态可以被丢弃。这在示例代码中是可能的，因为所需的所有信息都作为递归调用中的参数传递。外部调用中的变量不再需要，因此不需要在堆栈上保留任何内容。 由于不再需要外部调用的参数，因此递归调用可以转化为赋值：

(set! product (* counter product))
(set! counter (+ counter 1)
(set! max-count max-count)

然后它就跳到程序的开头。

Answer 2

(define
  (fact-iter-helper n accumulator)
  (cond
    ((< n 2) 1)
    (else (fact-iter-helper (- n 1) (* accumulator n)))
  )
)

(define
  (fact-iter n)
  (fact-iter-helper n 1)
)