NEWBIE: Recursion and iteration

Quote:

>I have two solutions to the same program

>--------------------------------------

>; recursion

>(define (rec-expt x y)

> (define (expt x y)

> (if (= y 0)

> 1

> (* x (expt x (- y 1)))))

> (if (>= y 0)

> (expt x y)

> (expt (/ 1 x) (abs y))))

>---------------------------------------

>;iteration

>(define (iter-expt x y)

> (define (iter y product)

> (if (= y 0)

> product

> (iter (- y 1)

> (* x product))))

> (if (>= y 0)

> (iter y 1)

> (/ 1 (iter (abs y) 1))))

>-----------------------------------------

>ok the first one is recursive and the second iterative but what is the

>difference? since the second (itarative) is also calling the same

>procedure "iter". Ok now how can we know exactly the difference

>between a recursive procedure and an iterative one?

The one you call "iteration" is actually recursive, but it's tail recursive

(see my answer to your previous message).

The important difference is that in rec-expt, the recursive call to expt is

not the last thing that expt does. After calling expt, it has to multiply

the result by x and return that. This means that each recursive call needs

its stack frame preserved, so that when it's resumed it can perform the

multiplication. iter, on the other hand, doesn't need to do anything when

the recursive call returns, so nothing in its stack frame needs to be

preserved during the recursive call. Instead, it can simply go back to the

beginning of the procedure and use the existing stack frame.

--

GTE Internetworking, Powered by BBN, Burlington, MA

*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.

Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.