induction on natural numbers
problem: exponentiation
- we want (exp x k) to evaluate to x to the power k, for int x and natural k
- write a simple recursive procedure to do this
solution
- write down a recursive definition of the natural numbers
a natural number is either
0, or
(i+1) where i is a natural number
- write down a recursive definition of the problem using the same structure
when k is (exp x k) is
0 1
i + 1 (* x (exp x i))
- note that when (= k (+ i 1)), (= i (- k 1))
- transcribe into code
(define (exp x k) (if (= k 0) 1 (* x (exp x (- k 1)))))