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/
Before you buy.



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
(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.



Sun, 05 May 2002 03:00:00 GMT  
 
 [ 2 post ] 

 Relevant Pages 

1. [TKTS] iteration vs recursion example

2. [TKTS] iteration vs recursion example

3. Recursion where iteration would do

4. understanding recursion vs iteration

5. iteration vs recursion question

6. iteration through recursion

7. iteration vs recursion Performance viewpoint

8. Recursion -> Iteration

9. Recursion vs Iteration

10. Iteration & car/cdr-recursion

11. iteration vs. recursion

12. RECURSION RECURSION RECURSION ... AAARRGGHHHH

 

 
Powered by phpBB® Forum Software