Quan Tong
"Life is all about sharing. If we are good at something, pass it on." - Mary Berry

SICP Exercise 1.16: Iterative Exponentiation

2021-09-29

I am reading SICP.

Section 1.2.4 talks about the problem of computing the exponential of a given number.

The authors start with a recursive procedure:

1#lang sicp
2
3(define (expt b n)
4    (if (= n 0)
5        1
6        (* b (expt b (- n 1)))))

This requires O(n) steps and O(n) space.

then an iterative procedure:

 1#lang sicp
 2
 3(define (expt b n)
 4    (expt-iter b n 1))
 5
 6(define (expt-iter b counter product)
 7    (if (= counter 0)
 8        product
 9        (expt-iter b
10                   (- counter 1)
11                   (* b product))))

Read More...