| Sussman and Steele | December 22, 1975 | 16 | Substitution Semantics and Styles |
Now, What About Iteration?
Consider the "iterative" definition of FACT. Although it appears to be recursive, since it "calls itself", we will see that it captures the essence of our intuitive notion of iteration.
(DEFINE FACT (LAMBDA (N) (LABELS ((FACT1 (LAMBDA (M ANS) (IF (= M 0) ANS (FACT1 (- M 1) (* M ANS)))))) (FACT1 N 1))))
Let us now compute (fact 3).
=> (FACT 3) => (FACT1 3 1) => (IF (= 3 0) 1 (FACT1 (- 3 1) (* 3 1))) => (FACT1 (- 3 1) (* 3 1)) => (FACT1 2 (* 3 1)) => (FACT1 2 3) => (IF (= 2 0) 3 (FACT1 (- 2 1) (* 2 3))) => (FACT1 (- 2 1) (* 2 3)) => (FACT1 1 (* 2 3)) => (FACT1 1 6) => (IF (= 1 0) 6 (FACT1 (- 1 1) (* 1 6))) => (FACT1 (- 1 1) (* 1 6)) => (FACT1 0 (* 1 6)) => (FACT1 0 6) => (IF (= 0 0) 6 (FACT1 (- 0 1) (* 0 6))) => 6
Notice that the expressions involved have a fixed maximum size independent of the argument to FACT! In fact, as Marvin Minsky pointed out, successive reductions produce a cycle of expressions which are identical except for the numerical quantities involved. Looking back, we may note by way of comparison that the recursive version caused creation of expressions proportional in size to the argument. This is why we think that this version of FACT is iterative rather than recursive. At each stage of the iterative version the "state" of the computation is summarized in two variables, the counter and the answer accumulator, while at each stage of the recursive version the "state" contains a chain of pieces each of which contains a component of the state. In the recursive version of FACT, for example, the state contains the sequence of multiplications to be performed upon return from the bottom. It is true that the iterative factorial also can produce expressions of arbitrary size, since
