SICP 1.14-1.15

习题1.14

习题1.15

(define (cube x) (* x x x))
(define (p x) (- (*  x) (*  (cube x))))
(define (sine angle)
   (if (not (> (abs angle) ))
       angle
       (p (sine (/ angle )))))
           

参照:

a)

Each time running the (sine angle) and fails the if, it’s reduced to (p (sine (/ angle 3.0))), using the application order, procedure p is defered and (sine (/ angle 3.0)) is evaluated. So the process is a linear recursion, and the times p is applied is the same as the steps for angle to go down under 0.1. When angle is 12.15, the answer is 5.

b)

Order of growth in space

space = theta(log(n)) because it is a linear recursion and the question go down 3 times each iteration.

Order of growth of steps

steps = theta(log(n)) because it is a linear recursion and the question go down 3 times each iteration.