Problem 1: Pow (100pts)

Implement a procedure pow for raising the number base to the power of a non-negative integer exp for which the number of operations grows logarithmically, rather than linearly (the number of recursive calls should be much smaller than the input exp). For example, for (pow 2 32) should take 5 recursive calls rather than 32 recursive calls. Similarly, (pow 2 64) should take 6 recursive calls.

Hint: Consider the following observations:

  1. \[ x^{2y} = (x^y)^2 \]
  2. \[ x^{2y+1} = x(x^y)^2 \]

For example we see that \( 2^{32} \) is \( (2^{16})^2 \), \( 2^{16} \) is \( (2^8)^2 \), etc. You may use the built-in predicates even? and odd?. Scheme doesn't support iteration in the same manner as Python, so consider another way to solve this problem.

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

(define (pow base exp)
  'YOUR-CODE-HERE
)

;;; Tests
; scm> (pow 2 3)
; 8