RE: [Dev-C++] recursion

[Ioannis V. <no...@ho...>]

-------Original Message-------=0D
 =0D
From: Per Westermark=0D
Date: =D0=E1=F1=E1=F3=EA=E5=F5=DE, 14 =D6=E5=E2=F1=EF=F5=DC=F1=E9=EF=F2 2=
003 10:35:36 =EC=EC=0D
To: Ioannis Vranos=0D
Cc: dev...@li...=0D
Subject: RE: [Dev-C++] recursion=0D
 =0D
Yes recursion devicient in comparison to loop.=0D
=0D
But factorial is special in thtat it's only a loop.=0D
=0D
For more advanced problems, you need a loop with a state-saving queue,=0D
with continuous push/pop. And then suddenly it isn't possible to easily=0D
say which alternative is faster.=0D
=0D
=0D
=0D
=3D=3D> I assume you mean for some specific problems. If i needed a queue=
 i
would use the std::queue from the standard library which would not have t=
he
stack limitations of the system. :)=0D
 =0D
 =0D
 =0D
For some problems, the cost of the crecursive call is smaller than the=0D
state-checking needed in the loop.=0D
 =0D
 =0D
=3D=3D> The above statement is very case-specific and also not so specifi=
c. :) A
more general statement which is always true is that in 100% of cases
recursion is more space deficient than iteration. Let's take an example o=
f a
recursive function with one argument. If we consider the impossible scena=
rio
that the iterative equivalent of it requires 10 variables, for calculatio=
ns
of 100 number depth, the recursive will occupy space for 100 variables wh=
ile
the loop for 10. A more realistic scenario of the above is 100 vs 3-5. Al=
so
all these calls are stored in the stack.=0D
 In run-time you get the continuous function calls and the object
instantiations.=0D
=0D
=0D
Besides, just about always, the hard-ware controlled overflow checking of=
=0D
a stack wins over manual check of software-implemented queue.=0D
=0D
Auto-allocation/deallocation on stack is also hardware-assisted. Just=0D
about the only case where a queue allocation matches speed of=0D
auto-allocation is when the queue is fixed-size and allocation is just=0D
queue_top++;=0D
=0D
Basically, speed and or memory consumption is normally not too big an=0D
issue between the two methods. The most important issue is if you manage=0D
to implement the code - and get it bug-free with one of the available=0D
alternatives.=0D
=0D
=0D
=3D=3D> I disagree, for generic problem solutions (that is for not specia=
l cases
specialisations) i consider the space/time deficiency of recursion in
comparison to loop very serious. Even for special cases, i still would
prefer a loop.=0D
=0D
=0D
Ioannis Vranos=0D
=0D
* Programming pages: http://www.noicys.freeurl.com=0D
* Alternative URL: http://run.to/noicys=20