NEWBIE: Recursion and iteration
Author Message
NEWBIE: Recursion and iteration

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?

Sent via Deja.com http://www.*-*-*.com/

Sun, 05 May 2002 03:00:00 GMT
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

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.

--