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:

#lang sicp

(define (expt b n)
    (if (= n 0)
        1
        (* b (expt b (- n 1)))))

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

then an iterative procedure:

#lang sicp

(define (expt b n)
    (expt-iter b n 1))

(define (expt-iter b counter product)
    (if (= counter 0)
        product
        (expt-iter b
                   (- counter 1)
                   (* b product))))

Read More...