SICP ex 1.16

プログラム

ヒントより、

ab^{n}=const

と成るような状態遷移を考える。

a(b_{i}^{2})^{\frac{n}{2}}

で、nが奇数のときaに押しつける。

(define (even? n)
  (= (remainder n 2) 0))
 
(define (square a) (* a a))

(define (fast-expt-iter b n a)
  (cond ((= n 0) a)
        ((even? n) (fast-expt-iter (square b) (/ n 2) a))
	(else (fast-expt-iter b (- n 1) (* a b)))))

(define (fast-expt b n)
  (if (even? n)
      (fast-expt-iter b n 1)
      (fast-expt-iter b (- n 1) 1)))

こんな感じかな？
関数型の言語を扱うのは初めてなので、なんか不思議な感じがした。
なんか、目の前がひろがった。なんとなく、schemeの考え方がわかった気がした。