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

并且说"我们将一个递归过程称为事实 - 因为生成一个迭代过程似乎令人不安.但是,这个过程确实是迭代的:它的状态完全被它的三个状态变量捕获,并且一个解释器需要跟踪只有三个变量才能执行这个过程."

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

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)

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