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

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

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

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屋！