sicp 1.16的答案

看了sipc前面一两节, 主要就明白了迭代和循环的不同.

习题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)² = (b²)^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 a bⁿ 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.)

用迭代实现的一个exp

(define square
  (lambda (x)
    (* x x)))

(define exp-iter
  (lambda (base n product)
    (cond ((= n 0) product)
          ((even? n) (exp-iter (square base) (/ n 2) product))
          (else (* base (exp-iter base (- n 1) product))))))
(define exp2
  (lambda (base n)
    (exp-iter base n 1)))

(exp2 2 10)

sicp在线版本