Chapter 5, Computing with Register Machines
Exercise 5.27
As in last exercise, let’s first see some results for various values of n:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
;;; EC-Eval input:
(factorial 1)
(total-pushes = 3 maximum-depth = 3)
;;; EC-Eval value:
ok
;;; EC-Eval input:
(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
;;; EC-Eval input:
Clearly the formulae is:
$$
\, \text{maximum-depth} = 5n+3 \,
$$
and
$$
\, \text{total-pushes} = 32(n-1) + 16 = 32n - 16 \,
$$
Thus we get the following table:
| Maximum depth | Number of pushes | |
|---|---|---|
| Recursive factorial | $\, \text{maximum-depth} = 5n+3 \,$ | $\, \text{total-pushes} = 32n - 16 \,$ |
| Iterative factorial | $\, \text{maximum-depth} = 10 \,$ | $\, \text{total-pushes} = 35n + 29 \,$ |