Recitation #7, Problems Done in Recitation, Fri., 9/12/97


1. The lecture neglected to analyze the number of arithmetic ops (these
ops are ZERO? + -) for tail-recursive fib.

(define (fast-fib n)
  (helper 1 0 n))

(define (helper a b n)
  (if (zero? n)
      b
      (helper (+ a b) a (- n 1))))

Note that the number of ops of (fast-fib n) is the number of ops of
(helper 1 0 n) and number of ops used by (helper a b n) depends only on n,
not a and b.  (Why?)  Let ops(n) be number of ops to eval (helper ? ? n).
Fill in for the dots to complete the equation
   ops(n) = ... ops(n-1)....

Now derive a simple arithmetic expression for ops(n).

   SOLN: ops(n) = 3 + ops (n-1) = 3 + 3 + 3 + ...n times + 1 = 3n+1
   LINEAR!

2. Using the "useful facts"

         b^0 = 1,
for n>0, b^n = b * b^(n-1),

design a recursive procedure EXPT such that (expt b n) returns b^n.
Indicate whether your procedure is tail-recursive (it does not have to
be).  Derive a simple arithmetic expression for ops(n) in this case.