Use the monitored stack to explore the tail-recursive property of the evaluator (section 5.4.2). Start the evaluator and define the iterative
procedure from section 1.2.1:
(define (factorial n) (define (iter product counter) (if (> counter n) product (iter (* counter product) (+ counter 1)))) (iter 1 1))
Run the procedure with some small values of
. Record the maximum stack depth and the number of pushes required to compute
for each of these values.
a. You will find that the maximum depth required to evaluate
is independent of
. What is that depth?
b. Determine from your data a formula in terms of
for the total number of push operations used in evaluating
n ≥ 1
. Note that the number of operations used is a linear function of
and is thus determined by two constants.
There are no comments yet.
You must log in to post a comment.Login