SICP Series-chapter 1.2.4

The exercises of this section focus on the exponentiation, which you can use the recursive method, meanwhile you can also use the iterative method. 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.
1.16
The recursive version of fast-expt:
(defun fast-expt(b n)
    (cond ((= n 0) 1)
          ((evenp n) (expt (fast-expt b (/ n 1))
                            2))
          (t (* b (fast-expt b (- n 1))))))
The iterative version of fast-expt:
(defun fast-expt-v2(b n)
    (fast-expt-iter b n 1))
 
(defun fast-expt-iter(b n a)
    (cond ((= n 0) a)
          ((evenp n) (fast-expt-iter (* b b) (/ n 2) a))
          (t (fast-expt-iter b (- n 1) (* a b)))))
1.17
The recursive version of fast-add:
(defun double(x)
    (* 2 x))
(defun halve(x)
    (/ x 2))
 
(defun newmultip-rec(a b)
    (cond ((= b 0) 0)
          ((= b 1) a)
          ((evenp b) (double (newmultip-rec a (halve b))))
          (t (+ a (newmultip-rec a (- b 1))))))
The iterative version of fast-add:
(defun newmultip(a b &optional (addtion 0))
    (cond ((= b 0) addtion)
          ((evenp b) (newmultip (double a) (halve b) addtion))
          (t (newmultip a (- b 1) (+ a addtion)))))