RE: [Dev-C++] recursion

[Louis G. <lg...@ya...>]

Greets,
Both of your comments raise interesting questions regarding how to
construct efficient run-time code. The simple recursion
     factorial(n)= n(n-1)..(1); 
is easily implemented as either a simple loop or recursion;
BUT could you guys comment on stack space, run-time etc. for a call 
like factorial(100) implemented as a recursion compared to a loop ? 

--- Ioannis Vranos <no...@ho...> wrote:
> -------Original Message-------
>  
> From: Per Westermark
> Date: ÐáñáóêåõÞ, 14 ÖåâñïõÜñéïò 2003 2:38:47 ìì
> To: Jaap de Wolff
> Cc: dev...@li...
> Subject: RE: [Dev-C++] recursion
>  
> I think you got a bit confused about terminology.
> 
> Looping and iteration is actually the same thing.
> 
> 
> ==> Yes you are right.
> 
> 
> 
> However, recursion is not anything that should be specifically avoided.
> It's a question of what problem to solve.
> 
> The trivial example of the faculty function seems to be the most quoted
> example for the use of a loop instead of recursion, but the example is
> quite bad, since it's faculty is easier to implement and runds faster as
> a
> loop.
> 
> There are matematical rules that makes it possible to rewrite any
> iterative function into a recursive function. And in the same way, any
> recursive function may be converted to use state queues to store the
> recursive state.
> 
> Use recursion when recursion results in faster run-time, or an easier
> implementation. In other cases, select an iterative approach.
> 
> 
> ==> Recursion resulting to faster run-time is something close to the
> impossible. I agree with the "easier implementation" + "while it does
> not
> introduce significant run-time and space costs".
> 
> 
> 
> Examples where recursion faster and/or easier:
> - light-tree evaluation in a ray tracer.
> - parsing of mathematical expressions
> - some recursively defined functions, such as Ackerman
> - regular expression pattern matching
> 
> 
> ==> The "faster" thing is tough to prove. I agree with the "easier".
> 
> 
> 
> Ioannis Vranos
> 
> * Programming pages: http://www.noicys.freeurl.com
> * Alternative URL: http://run.to/noicys 


__________________________________________________
Do you Yahoo!?
Yahoo! Shopping - Send Flowers for Valentine's Day
http://shopping.yahoo.com