#lang racket
;;; Exploring Languages with Interprters and Functional Programming
;;; Chapter 9: Recursion Styles and Efficiency -- Exponentiation
;;; H. Conrad Cunningham

;;; 567890123456789012345678901234567890123456789012345678901234567890

;;; Adapted slightly from SCIP 1.2.4 for DrRacket Scheme

(define (expt3 b n)
  (cond ((< n 0)
    (error `expt3 "Called with negative exponent"))
    (else (expt_iter b n))))

(define (expt_iter b n)
  (cond ((= n 0) 1)
        ((even? n) (square (expt3 b (/ n 2))))
        (else (* b (expt3 b (- n 1))))))

(define (square x) (* x x))

(define (even? n)
  (= (remainder n 2) 0))