recursion - SICP递归过程与迭代过程: using a recursive procedure to generate an iterative process

Question

SICP中的Section 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)))

并说 “我们将诸如事实事实之类的递归过程称为生成迭代过程似乎令人不安。但是，该过程实际上是迭代的:其状态被其三个状态变量完全捕获，并且解释器需要保持仅跟踪三个变量以执行该过程。”

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

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)

然后它就跳到过程的开始。