SICP Exercise 1.16 - Is my solution correct?

Question

Exercise 1.16: Design a procedure that evolves an iterative exponentiation process that uses successive squaring and uses a logarithmic number of steps, as does fast-expt. (Hint: Using the observation that (b(^n/2))^2 = (b(^2))^n/2 , keep, along with the exponent n and the base b, an additional state variable a, and define the state transformation in such a way that the product ab^n is unchanged from state to state. At the beginning of the process a is taken to be 1, and the answer is given by the value of a at the end of the process. In general, the technique of defining an invariant quantity that remains unchanged from state to state is a powerful way to think about the design of iterative algorithms.)

So I've tried really hard and came up with this solution:

(define (exp b n)
  (exp-iter b n 1))

(define (square p) (* p p))

(define (even? k)
  (= (remainder k 2) 0))

(define (exp-iter b counter product)
  (define (smash counter)
    (if (even? counter) (square (exp-iter b (/ 2 counter) product)) (* b (exp-iter b (- counter 1) product))))
  (if (= counter 0) product (smash counter)))

(exp 4 3) ;test

This runs perfectly but I'm not sure if this is what the author asked me to do. Are there any problems with this? Is my solution really iterative?

Answer 1

Your solution is not iterative. An iterative process is one that doesn't call anything after the recursive call, and that's not the case in these two lines:

(square (exp-iter b (/ 2 counter) product))
(* b (exp-iter b (- counter 1) product))

After invoking exp-iter, in the first line you're passing the result to square, and in the second line you're multiplying the result by b. Compare it with this, a tail recursive solution:

(define (exp-iter b counter product)
  (cond ((= counter 0)
         product)
        ((even? counter)
         (exp-iter (square b) (/ counter 2) product))
        (else
         (exp-iter b (- counter 1) (* b product)))))

Notice that after invoking exp-iter there's nothing left to do and the procedure simply returns its value. A smart compiler will detect this, and transform the recursive call into a loop that will use a constant amount of stack memory (instead of increasing with every recursive call.)