5.14 Exercise 5.14

We are asked to run the recursive factorial program through the interpreter with stack statistics enabled, deriving a formula for the relationship between n and the number of stack operations and the maximum depth of the stack during the execution of the program.

We should expect to see a linear relationship between both of these and the input size, because the program recurses by repeatedly subtracting one from the input. Let’s verify that.

First, here’s an instrumented version of the factorial program that initializes the stack at the beginning of the program and prints the stack statistics at the end:

(define recursive-factorial-machine

(make-machine

(list (list '= =) (list '- -) (list '* *))

'(controller

(perform (op initialize-stack))

(assign continue (label fact-done))

fact-loop

(test (op =) (reg n) (const 1))

(branch (label base-case))

(save continue)

(save n)

(assign n (op -) (reg n) (const 1))

(assign continue (label after-fact))

(goto (label fact-loop))

after-fact

(restore n)

(restore continue)

(assign val (op *) (reg n) (reg val))

(goto (reg continue))

base-case

(assign val (const 1))

(goto (reg continue))

fact-done

(perform (op print-stack-statistics)))))

Next, let’s run the machine for the integers from 1 to 30:

(define (build-list n proc)

(define (acc vals next)

(if (> 0 next)

vals

(acc (cons (proc next) vals) (- next 1))))

(acc '() (- n 1)))

As predicted, there is a strict linear relationship between the number of pushes (and the maximum depth of the stack) and n – in this case, with the number of pushes and the maximum stack depth being 2 * (n - 1).