A stack remembers what must happen after return.
An explicit stack can hold the multipliers that a recursive factorial process would otherwise leave in pending calls.
What information does a machine save while it descends into a recursive problem?
- Move pending multiplication onto an explicit stack
- Use a phase register to distinguish descent from return
- Connect stack depth with suspended work
During descend, the machine pushes n and continues with n minus one. At the base case it places 1 in value and switches the phase to return.
During return, each transition pops one saved multiplier and updates value. An empty stack means no suspended multiplication remains, so value is the final answer.
(begin
(define (run n stack value phase steps)
(cond ((eq? phase 'descend)
(if (= n 1)
(run n stack 1 'return (+ steps 1))
(run (- n 1) (cons n stack) value
'descend (+ steps 1))))
((null? stack) (list value steps))
(else
(run n (cdr stack) (* (car stack) value)
'return (+ steps 1)))))
(run 5 '() 0 'descend 0))- Output
- —
- Value
- —
- Diagnostic
- —
The first program returns (120 9). The machine performs five descent transitions and four stack pops.
Find the point where phase changes from descend to return. Before it, stack grows by cons. After it, stack shrinks by cdr as value grows.
Change the program before you read the hint.
Run the machine for 6 and predict both the factorial value and the number of transitions.
Show one hint
There are n descent transitions and n minus one return transitions.