Recursive version:
(define (square x) (* x x))
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (square (expmod base (/ exp 2) m))
m))
(else
(remainder (* base (expmod base (- exp 1) m))
m))))
I was a bit surprised that the above algorithm didn’t come with the problem set of to rewrite it in an iterative form. So here it is.
Iterative Version:
(define (square-mod n m) (remainder (* n n) m))
(define (expmod-iter base n m a)
(cond ((= n 0) a)
((even? n) (expmod-iter (square-mod base m) (/ n 2) m a))
(else
(expmod-iter base (- n 1) m (remainder (* a base) m)))))
(define (expmod base n m)
(expmod-iter base n m 1))