Turning a recursive procedure to a iterative procedure - SICP exercise 1.16

Question

In the book Structure and interpretation of computer programs, there is a recursive procedure for computing exponents using successive squaring.

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

Now in exercise 1.16:

Exercise 1.16: Design a procedure that evolves an iterative exponentiation process that uses successive squaring and uses a logarithmic number of steps, as does `fast-expt`. (Hint: Using the observation that
(b(^n/2))^2 = (b(^2))^n/2
, keep, along with the exponent n and the base b, an additional state variable a, and define the state transformation in such a way that the product ab^n is unchanged from state to state. At the beginning of the process a is taken to be 1, and the answer is given by the value of a at the end of the process. In general, the technique of defining an invariant quantity that remains unchanged from state to state is a powerful way to think about the design of iterative algorithms.)

I spent a week and I absolutely can't figure how to do this iterative procedure, so I gave up and looked for solutions. All solutions I found is this:

(define (fast-expt a b n)
    (cond ((= n 0) 
        a)
    ((even? n) 
        (fast-expt a (square b) (/ n 2)))
   (else 
        (fast-expt (* a b) b (- n 1)))))

Now, I can understand

        (fast-expt a (square b) (/ n 2)))

using the hint from the book, but my brain exploded when n is odd. In the recursive procedure, I got why

        (* b (fast-expt b (- n 1))))))

works. But in the iterative procedure, it becomes totally different,

        (fast-expt (* a b) b (- n 1)))))

It's working perfectly but I absolutely don't understand how to arrive at this solution by myself. it seems extremely clever.

Can someone explain why the iterative solution is like this? And what's the general way to think of solving these types of problems?

2021 update: Last year, I completely forgot about this exercise and the solutions I've seen. I tried solving it and I finally solved it on my own using the invariant provided in the exercise as a basis for transforming the state variables. I used the now accepted answer to verify my solution. Thanks @Óscar López.

lol, I spent 30 minutes and got frustrated. You must have amazing perseverance to have spent a week on this. — qiu
@qiu it depends. On average, I spent from a week to a month solving an exercise from this book. For example, I spent almost 7 months solving exercise 1.11. I put up with it because I almost always learned something after solving them. The long time that I gave them is always worth it in the end. This is an exception because I am actually very easily distracted and frustrated if I find something to be borring. — lightning_missile

Óscar López Óscar López · Accepted Answer · 2015-11-22T14:44:20

Here's a slightly different implementation for making things clearer, notice that I'm using a helper procedure called loop to preserve the original procedure's arity:

(define (fast-expt b n)
  (define (loop b n acc)
    (cond ((zero? n) acc)
          ((even? n) (loop (* b b) (/ n 2) acc))
          (else (loop b (- n 1) (* b acc)))))
  (loop b n 1))

What's acc in here? it's a parameter that is used as an accumulator for the results (in the book they name this parameter a, IMHO acc is a more descriptive name). So at the beginning we set acc to an appropriate value and afterwards in each iteration we update the accumulator, preserving the invariant.

In general, this is the "trick" for understanding an iterative, tail-recursive implementation of an algorithm: we pass along an extra parameter with the result we've calculated so far, and return it in the end when we reach the base case of the recursion. By the way, the usual implementation of an iterative procedure as the one shown above is to use a named let, this is completely equivalent and a bit simpler to write:

(define (fast-expt b n)
  (let loop ((b b) (n n) (acc 1))
    (cond ((zero? n) acc)
          ((even? n) (loop (* b b) (/ n 2) acc))
          (else (loop b (- n 1) (* b acc))))))

Turning a recursive procedure to a iterative procedure - SICP exercise 1.16

1 Answers