5.1.4 · Saving suspended work

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.

Guiding question

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.

SICP code428 of 1,048,576 UTF-8 bytes

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

Examples

Result—

Output: —
Value: —
Diagnostic: —

Execution trace0 / 0 events

Expected result

The first program returns (120 9). The machine performs five descent transitions and four stack pops.

Trace focus

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.

Try it yourself

Change the program and compare the result.

Run the machine for 6 and predict both the factorial value and the number of transitions.

Show hint

There are n descent transitions and n minus one return transitions.

Complete this lesson

0 of 23 lessons complete in this chapter0%