Chapter 1, Building Abstractions with Procedures
Section - Procedures and the Processes They Generate
Exercise 1.10
1
2
3
4
5
6
(define (A x y)
(cond ((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A (- x 1)
(A x (- y 1))))))
Output returned by given statements:
1
2
3
4
5
6
(A 1 10)
; 1024
(A 2 4)
; 65536
(A 3 3)
; 65536
Mathematical definition for:
1
(define (f n) (A 0 n))
Clearly it is: $2n$
Mathematical definition for:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
(define (f n) (A 1 n))
; We expand the function until it reaches to the most primitive form.
(A 1 n)
(A 0 (A 1 n-1))
(A 0 (A 0 (A 1 n-2)))
(A 0 (A 0 (A 0 (A 1, n-3)))
....
....
(A 0 (A 0 .... (A 1 n - (n-1) ))))))
(A 0 (A 0 .... (A 1 1))))))
(A 0 (A 0 .... 2)))))
(A 0 (A 0 .... (* 2 2))))))
A(0, A(0, .... (* 2 (* 2 2)))))
...
(* 2 (* 2 (* 2 .... n times)))
Clearly it is: $2^n$.
Mathematical definition for:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(define (f n) (A 2 n))
; We expand the function until it reaches to the most primitive form.
(A 2 n)
(A 1 (A 2 n-1))
(A 1 (A 1 (A 2 n-2)))
...
(A 1 (A 1 ... (A 2 1)))
(A 1 (A 1 ... (A 1 2)))
; We know A(1, n) is 2^n
(A 1 (A 1 ... (A 1 2)))
(^ 2 (^ 2 (^ 2 ...) n times
Clearly it is:
$$
= 2^{2^{2^ ... \text{ n times}}}
$$