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

Question

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

10

在 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这样的递归过程称为生成迭代过程可能看起来令人不安。然而，该过程确实是迭代的：它的状态完全由其三个状态变量捕获，并且解释器只需要跟踪这三个变量即可执行该过程。”

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

- zuozuo

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Barmar · Accepted Answer

一个递归过程需要在递归调用进行时保持调用者的状态。例如，如果您编写了以下代码：

(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)

然后它就跳到了该过程的开头。