CODEWITHSUNDEEP
schemesicp
Wizard
Wizard

Reputation: 22093

Fixed number and fixed rule in iterative process

I am reading 1.2 Procedures and the Processes They Generate of SICP.

A linear iterative process to computing factorial 

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

Iteration:
product <--- counter · product
counter <--- counter + 1

Then illustrate that:

At each step, all we need to keep track of, for any =n=, are the current values of the variables product, counter, and max-count. We call this an iterative process. In general, an iterative process is one whose state can be summarized by
1) a fixed number of state variables,
2) together with a fixed rule that describes how the state variables should be updated as the process moves from state to state
3) and an (optional) end test that specifies conditions under which the process should terminate. In computing n!, the number of steps required grows linearly with n. Such a process is called a linear iterative process.

Reference to the 1) fixed number 2) fixed rule and 3)optional end test

When I could confirm is that max-countis the 3) optional end test. but I am not sure about the fix number and fixed rule.

If fixed number is counter then fixed rule is product=counter * product, in this situation, counter is not fixed, it is counter += 1

If fixed number is counter and fixed rule is counter + 1, then they omit the greater rule of product and are too trivial.

What's the fixed number and fixed rule appropriately?

Upvotes: 0

Views: 36

Answers (1)

&#211;scar L&#243;pez
&#211;scar L&#243;pez

Reputation: 236004

In this context, a "fixed number" of variables means that there's a limited number of variables, known in advance when the process starts - we just have three of them: product counter and max-count. This is in contrast with a recursive process, which will have new copies of those three variables per procedure call in stack frames.

The second point is related: a "fixed rule" refers to the fact that in the recursive step of the procedure we simply call fact-iter, and there's nothing left to do after it executes: in other words, it's in tail position.

Upvotes: 1

Related Questions