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 (bn/2)2 = (b2)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 bn 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.)
一个迭代式的、只具有对数时间复杂度的 expt 函数如下：
(define (fast-expt-iter b n)
(define (fast-expt-iter-helper b n a)
(cond ((= n 0) a)
((even? n) (fast-expt-iter-helper (* b b) (/ n 2) a))
(else
(fast-expt-iter-helper b (- n 1) (* a b)))))
(fast-expt-iter-helper b n 1))
题目中提到了思考迭代式的思维方式。因为每次迭代都必须记录当前的计算结果，所以必须在参数中有一个“不变量”，这个不变量即为当前的计算结果。