SICP 1.16
(define (my-expt b n) (define (expt-iter a n) (cond ((= n 1) #?=a) ((even? n) #?=(expt-iter (* a a) (/ n 2))) (else #?=(* a (expt-iter a (- n 1)))))) (expt-iter b n)) (print (my-expt 3 8))
結果は正しいけど、解き方は間違っているっぽい。
else節で後でaを掛けたらiterativeにならないもんなぁ。
というわけでもう一度考えてみた。要は途中状態を保存する変数を引数として追加すれば良いのだろう。
a ^ n => 1 * a ^ n
a ^ 2n => 1 * (a*a) ^ n
a ^ (n + 1) => a * a ^ n
(define (my-expt b n) (define (expt-iter k a n) (cond ((= n 1) (* k a)) ((even? n) (expt-iter k (* a a) (/ n 2))) (else (expt-iter (* k a) a (- n 1))))) (expt-iter 1 b n))