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 \,$