RE: [Dev-C++] recursion

[Per W. <pw...@ia...>]

Yes recursion devicient in comparison to loop.

But factorial is special in thtat it's only a loop.

For more advanced problems, you need a loop with a state-saving queue,
with continuous push/pop. And then suddenly it isn't possible to easily
say which alternative is faster.

For some problems, the cost of the crecursive call is smaller than the
state-checking needed in the loop.

Besides, just about always, the hard-ware controlled overflow checking of
a stack wins over manual check of software-implemented queue.

Auto-allocation/deallocation on stack is also hardware-assisted. Just
about the only case where a queue allocation matches speed of
auto-allocation is when the queue is fixed-size and allocation is just
queue_top++;

Basically, speed and or memory consumption is normally not too big an
issue between the two methods. The most important issue is if you manage
to implement the code - and get it bug-free with one of the available
alternatives.

 /Per W

On Fri, 14 Feb 2003, Ioannis Vranos wrote:

> -------Original Message-------
>
> From: Louis Godio
> Date: =D0=E1=F1=E1=F3=EA=E5=F5=DE, 14 =D6=E5=E2=F1=EF=F5=DC=F1=E9=EF=F2 2=
003 4:57:27 =EC=EC
> To: Ioannis Vranos; dev...@li...
> Cc: dev...@li...
> Subject: RE: [Dev-C++] recursion
>
> Greets,
> Both of your comments raise interesting questions regarding how to
> construct efficient run-time code. The simple recursion
> factorial(n)=3D 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 ?
>
>
> =3D=3D> Of course. Recursion is very much run-time/space deficient in com=
parison
> to loop.
>
>
>
> Ioannis Vranos
>
> * Programming pages: http://www.noicys.freeurl.com
> * Alternative URL: http://run.to/noicys