CODEWITHSUNDEEP
schemeracket
user2909199
user2909199

Reputation: 49

Iterative version of recursive exponent function

I basically need to do a iterative version of the following function which i've already made:

(define (expo base e)
  (cond ((or (= base 1) (= e 0)) 1)
        (else (* base (expo base (- e 1))))))

im not sure how to so i need help(in racket/scheme))

Upvotes: 0

Views: 1766

Answers (3)

GoZoner
GoZoner

Reputation: 70175

As others have noted, a tail recursive algorithm is an iterative algorithm. However, perhaps you need an explicit iterative algorithm?

(define (expo base exp)
  (do ((acc   1 (* acc base))
       (exp exp (- exp 1)))
      ((= 0 exp) acc))))

One could add a condition for (= base 1) - but, as written, this is a simple as it gets. Assumes exp is an integer.

Upvotes: 0

Óscar López
Óscar López

Reputation: 236034

All you have to do is pass the result around in an accumulator. For that you need an extra parameter, there are several ways to do it, for example using an inner helper procedure:

(define (expo base e)
  ; helper procedure
  (define (iter e acc)
          ; now the base case returns the accumulator
    (cond ((or (= base 1) (= e 0)) acc) 
          ; see how the result is accumulated in the parameter
          (else (iter (- e 1) (* base acc)))))
  ; at the beginning, initialize the parameter in the right values
  (iter e 1))

Alternatively, we can use a named let for the same effect:

(define (expo base e)
  (let iter ((e e) (acc 1))
    (cond ((or (= base 1) (= e 0)) acc)
          (else (iter (- e 1) (* base acc))))))

It's good to differentiate between recursive procedures and processes. Both of the above implementations are recursive procedures: syntactically, it's easy to see that they call themselves. But the processes they generate are iterative: they're written in a tail recursive style, so after each recursive call ends there's nothing left to do, and the compiler can optimize away the recursive call and, for all practical purposes, transform it into an iterative loop.

To better understand how iteration works in Scheme read more about this subject in the fantastic SICP book, in the section Procedures and the Processes They Generate

Upvotes: 1

daniel gratzer
daniel gratzer

Reputation: 53881

The general pattern with converting such recursive functions to iteration is to use an accumulator

(define (expo base e)
   (define (go base e accum)
      (if (or (= base 1) (= e 0))
          accum
          (go base (- e 1) (* accum base)))) ; Now this is tail recursion
    ???)

Where ??? calls go with the appropriate initial value of accum. Notice how before the recusive call was inside another call (namely *) but now it's the last thing called. This allows for the program to run in constant space.

Upvotes: 1

Related Questions