Exercises

Exercise 1.14

Draw the tree illustrating the process generated by the count-change/1 function of the section Tree Recursion in making change for 11 cents. What are the orders of growth of the space and number of steps used by this process as the amount to be changed increases?

Exercise 1.15

The sine of an angle (specified in radians) can be computed by making use of the approximation $sin\ x \approx x$ if $x$ is sufficiently small, and the trigonometric identity

$$sin \ r = 3 sin \frac{r}{3} - 4 sin^3 \frac{r}{3}$$

to reduce the size of the argument of $sin$. (For purposes of this exercise an angle is considered "sufficiently small" if its magnitude is not greater than 0.1 radians.) These ideas are incorporated in the following functions:

(defun cube (x) (* x x x))

(defun p (x) (- (* 3 x) (* 4 (cube x))))

(defun sine (angle)
   (if (not (> (abs angle) 0.1))
       angle
       (p (sine (/ angle 3.0)))))

a. How many times is the function p/1 called when (sine 12.15) is evaluated?

b. What is the order of growth in space and number of steps (as a function of a) used by the process generated by the sine/1 function when (sine a) is evaluated?