| Sussman and Steele | December 22, 1975 | 17 | Substitution Semantics and Styles |
the number of bits needed to express factorial of n grows with n; but this is a property of the numbers calculated by the function which is implemented in iterative style, and not of the iterative control structure itself. A recursive control structure inherently creates expressions of unbounded size as a function of the recursion depth, while an iterative control structure produces a cycle of equivalent expressions, and so the expressions are of approximately the same size no matter how many iteration steps are taken. This is the essence of the difference between the notions of iteration and recursion. Hewitt [MAC, p. 234][1] made a similar observation in passing, expressing the difference in terms of storage used in program execution rather than in terms of intermediate expressions produced by substitution semantics.
Continuation Passing Recursion
Remember the other way to compute factorials?
(DEFINE FACT (LAMBDA (N C) (IF (= M 0) (C 1) (FACT (- N 1) (LAMBDA (A) (C (* N A)))))))
This looks iterative on the surface! but in fact it is recursive. Let's compute (FACT 3 ANSWER), where ANSWER is a continuation which is to receive the result of FACT applied to 3; that is, the last thing FACT should do is apply the continuation ANSWER to its result.
=> (FACT 3 ANSWER) => (IF (= 3 0) (ANSWER 1) (FACT (- 3 1) (LAMBDA (A) (ANSWER (* 3 A))))) => (FACT (- 3 1) (LAMBDA (A) (ANSWER (* 3 A)))) => (FACT 2 (LAMBDA (A) (ANSWER (* 3 A)))) => (IF (= 2 0) ((LAMBDA (A) (ANSWER (* 3 A))) 1) (FACT (- 2 1) (LAMBDA (A) ((LAMBDA (A) (ANSWER (* 3 A))) (* 2 8))))) => (FACT (- 2 1) (LAMBDA (A) ((LAMBDA (A) (ANSWER (* 3 A))) (* 2 A)))) => (FACT 1 (LAMBDA (A) ((LAMBDA (A) (ANSWER (* 3 A))) (* 2 A))))
- ↑ [MAC]
Project MAC Progress Report XI (July 1973 - July 1974). Project MAC, MIT (Cambridge, 1974).
