Exercise 5.27. For comparison with exercise 5.26, explore the behavior of the following procedure for computing factorials recursively:
(define (factorial n)
(if (= n 1)
1
(* (factorial (- n 1)) n)))
By running this procedure with the monitored stack, determine, as a function of n, the maximum depth of the stack and the total number of pushes used in evaluating n! for n > 1. (Again, these functions will be linear.) Summarize your experiments by filling in the following table with the appropriate expressions in terms of n:
============= =================== ======================
func maximum depth number of pushes
============= =================== ======================
recursive
------------- ------------------- ----------------------
iterative
============= =================== ======================The maximum depth is a measure of the amount of space used by the evaluator in carrying out the computation, and the number of pushes correlates well with the time required.
运行之后我们可以得到如下结果
;;; EC-Eval input:
(define (factorial n)
(if (= n 1)
1
(* (factorial (- n 1)) n)))
(total-pushes = 3 maximum-depth = 3)
;;; EC-Eval value:
ok
;;; EC-Eval input:
(factorial 1)
(total-pushes = 16 maximum-depth = 8)
;;; EC-Eval value:
1
;;; EC-Eval input:
(factorial 2)
(total-pushes = 48 maximum-depth = 13)
;;; EC-Eval value:
2
;;; EC-Eval input:
(factorial 3)
(total-pushes = 80 maximum-depth = 18)
;;; EC-Eval value:
6
;;; EC-Eval input:
(factorial 4)
(total-pushes = 112 maximum-depth = 23)
;;; EC-Eval value:
24
;;; EC-Eval input:
(factorial 5)
(total-pushes = 144 maximum-depth = 28)
;;; EC-Eval value:
120
;;; EC-Eval input:
(factorial 6)
(total-pushes = 176 maximum-depth = 33)
;;; EC-Eval value:
720
pushes 的关系是
============= =================== ======================
func maximum depth number of pushes
============= =================== ======================
recursive 5n+3 32n-16
------------- ------------------- ----------------------
iterative 10 35n+29
============= =================== ======================