CODEWITHSUNDEEP
sicp
Hibiki
Hibiki

Reputation: 11

Is this program recursive or iterative?

I started reading SICP and have a doubt 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.

The hint was to introduce an additional state variable a and perform the state transformation such that the product ab^n is unchanged. My first attempt went in a different direction:

(define (exp b n)
        (cond ((= n 1) b)
              ((even? n) (exp (square b) (/ n 2)))
              (else (* b (exp (square b) (/ (- n 1) 2))))))
(define (square x) (* x x))
(define (even? x) (= (remainder x 2) 0))

Now, as far as I understand, when n is a power of 2, the process has to be iterative since all information is passed down as state variables and the processor does not have to remember anything. Else, at some point, it has to remember to multiply b and it seems to be having recursive flavor (as it is calling a function while remembering to do something beyond just executing the new function but again this is different from other recursive processes I have seen in that this "recursive" step happens only if the current n is odd, not every time) . So is this process considered iterative or recursive? Is there a clear distinction between the two processes?

I might have abused the terminology (as I am trying to teach myself and am picking up words), but hope the intention is clear.

Upvotes: 1

Views: 37

Answers (0)

Related Questions