SICP 递归过程与迭代过程:使用递归过程生成迭代过程 [英] SICP recursive process vs iterative process: using a recursive procedure to generate an iterative process

问题描述

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

in SICP Section 1.2.1 The author giving such a code example below to show how to using iterative process to solve the factorial problem:

(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 之类的递归过程称为生成迭代过程，这似乎令人不安.但是，该过程确实是迭代的:它的状态完全由它的三个状态变量和一个解释器捕获只需跟踪三个变量即可执行流程."

不明白作者什么意思.递归过程和递归过程有什么区别?为什么他说下面的递归过程会生成一个迭代过程?

I don't understand what the author mean. What's the difference between a recursive procedure and a recursive process? And why did he say the recursive procedure below generating an iterative process?

推荐答案

递归过程需要在递归调用过程中维护调用者的状态.例如，如果您写道:

A recursive process needs to maintain the state of the caller while the recursive call is in progress. For instance, if you wrote:

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

外部调用必须记住 n 并等待内部调用返回，然后才能执行乘法.如果您调用 (fact-recurse 10)，当函数到达递归结束时，将有 9 个堆叠乘法待处理.

the outer call has to remember n and wait for the inner call to return before it can perform the multiplication. If you call (fact-recurse 10) there will be 9 stacked multiplications pending when the function reaches the end of its recursion.

但是在迭代过程中，可以丢弃较早的状态.这在示例代码中是可能的，因为所需的所有信息都作为递归调用中的参数传递.不再需要外部调用中的变量，因此无需在堆栈中保留任何内容.

But in an iterative process, the earlier state can be discarded. This is possible in the example code because all the information needed is passed as parameters in the recursive call. The variables in the outer call are no longer needed, so nothing needs to be kept on a stack.

由于不再需要外部调用的参数，递归调用可以转化为赋值:

Since the outer call's parameters are no longer needed, the recursive call can be translated into assignments:

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

然后它只是跳转到程序的开头.

and then it just jumps to the beginning of the procedure.

这篇关于SICP 递归过程与迭代过程:使用递归过程生成迭代过程的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！