The answer is only the last frame.
Two procedures can compute the same mathematical function while generating very different computational processes.
What makes a recursive process different from an iterative one?
- Distinguish recursive syntax from recursive process growth
- Recognize an explicit state carried by an iterative process
- Use a bounded trace to inspect process shape
The recursive version postpones multiplication until the smaller factorial returns. Its deferred work grows with n. The iterative version carries the partial product and counter as complete state.
Both definitions are recursive procedures because each calls itself. Only the second generates an iterative process whose state can be summarized by a fixed number of variables.
(letrec ((factorial
(lambda (n product)
(if (= n 0)
product
(factorial (- n 1) (* n product))))))
(factorial 8 1))- Output
- —
- Value
- —
- Diagnostic
- —
Both programs return 40320.
Compare the order of calls and multiplications. The bounded trace is a view of this run, not a proof of resource use for every input.
Change the program before you read the hint.
Run both examples with 5. For the iterative version, write down n and product before each call.
Show one hint
At every step, product times n factorial remains equal to the original factorial problem.