1.9:

(define (+ a b)
 (if (= a 0) b (inc (+ (dec a) b))))

(+ 4 5)
(if (= 4 0) 4 (inc (+ (dec 4) 5)))
(inc (+ 3 5))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9

Recursive


(define (+ a b)
 (if (= a 0) b (+ (dec a) (inc b))))

(+ 4 5)
(+ 3 6)
(+ 2 7)
(+ 1 8)
(+ 0 9)
9

Iterative


1.10:

(define (A x y)
 (cond ((= y 0) 0)
       ((= x 0) (+ 2 y))
       ((= y 1) 2)
       (else (A (- x 1)
       	     	(A x (- y 1))))))

(A 1 10)
(A 0 (A 1 9))
(A 0 (A 0 (A 1 8)))
(A 0 (A 0 (A 0 (A 1 7))))
(A 0 (A 0 (A 0 (A 0 (A 1 6)))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1)))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 6)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 10))))))
(A 0 (A 0 (A 0 (A 0 12)))))
(A 0 (A 0 (A 0 14))))
(A 0 (A 0 16)))
(A 0 18)
22

(A 2 4) = 16
(A 3 3) = 16


1.34

(define (f g) (g 2))

(f f) gives error Error: call of non-procedure: 2. This is because it is expecting the 
second argument to be a procedure (implicitly from the fact that it applies it to 2).


1.35

Golden ratio: phi = (1 + sqrt(5))/2

Let x' be a fixed point of x |-> 1 + 1/x.  Then

x' = 1 + 1/x' = (x' + 1)/x'
x'^2 = x' + 1
x'^2 - x' - 1 = 0

Solutions: (1 +- sqrt(1 + 4)) / 2.  So phi is one of the fixed points.


2.64

partial-tree parititions the list into a left tree, the node, and a right tree.  This
is done such that the node is of size 1 and the left and right are equal for an odd-sized
list and left is 1 smaller than right for an even sized list.  partial-tree is then called
on the left and right sub trees.  The base case for the recursion is when the left and right
trees are both of size 0.  In this case, partial tree returns a leaf node (i.e. with null
left and right pointers).

Each element of the list is visited once, and for each visit, make-tree is called (which is
just a call to list, which is assumed to be O(1)).  So list->tree is O(n).


2.77

It is necessary to call apply-generic for each layer of tagged data.  Previously
there were only generic functions defined for complex data tagged with 'rect or
'polar.  Adding the complex package means we call apply-generic once for the complex
tag and then again for the 'rect or 'polar tag, using the same real-part, imag-part,
magnitude and angle functions.  This works because these are defined in terms of
apply-generic, which in turn uses the package definition.

For z as in the example,
(magnitude z)
(apply-generic 'magnitude z)
(magnitude ('rectangular 3 . 4))
(apply-generic 'magnitude ('rectangular 3 . 4))
(sqrt (+ (square 3) (square 4)))
5


3.27

For i = 0 or 1, (memo-fib i) is O(1). For i > 1, it is n additions.  This is because
for each i, (memo-fib i) is only calculated once.  This calculation is O(n) and each subsequent
lookup is O(1).  So, even though (memo-fib i) is called multiple times for each i, only i additions are
done for each.

This scheme will not work if we use (define memo-fib (memoize fib)).  The fib procedure is
defined recursively in terms of itself, and each of the these recursive calls will be evaluated in
an environment whose enclosing environment is the global environment.  This explicitly does not include
the table of pre calculated results, so we will not get the benefit of this.  Defining memo-fib recursively
in terms of itself means that the recursive calls are evaluated in an environment whose enclosing
environment is one where memoize has been evaluated, and thus it contains the table.  This is critical
to make the memoization work as required.