SICP recursive process vs iterative process: using a recursive procedure to generate an iterative process

Question

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

and say "It may seem disturbing that we refer to a recursive procedure such as fact-iter as generating an iterative process.However, the process really is iterative: Its state is captured completely by its three state variables, and an interpreter need keep track of only three variables in order to execute the process."

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?

Barmar Barmar · Accepted Answer · 2013-06-22T19:33:38

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

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 recursive process vs iterative process: using a recursive procedure to generate an iterative process

1 Answers