Menu
▾
▴
dev-cpp-users
|
From: Jaap de W. <wo...@Ne...> - 2003-02-14 12:22:02
|
> -----Original Message-----
> From: Ioannis Vranos [mailto:no...@ho...]
> Sent: Friday, February 14, 2003 07:25 AM
> To: dev...@li...
> Subject: Re: [Dev-C++] recursion
>=20
>=20
> -------Original Message-------
> =20
> From: Santiago
> Date: =D0=E1=F1=E1=F3=EA=E5=F5=DE, 14 =
=D6=E5=E2=F1=EF=F5=DC=F1=E9=EF=F2 2003 5:53:20 =F0=EC
> To: dev-cpp-users-list
> Subject: [Dev-C++] recursion
> =20
> Hello all,
> Simple one: how often, critical, and necessary is the usage=20
> of C++ recursion
> in the "real world" programming field?
> =20
> =20
> =3D=3D> It has its uses, but try to avoid using it. Use loops=20
> instead (usually
> iteration).
> =20
> =20
> =20
> Ioannis Vranos
Iteration is usefull when you have to make more of the same (iterative)
operations on the result of itself, before you have your result.
A traditional example of anything which can't be solved without =
iteration is
the resolving of a regular expression.
But of course there are more simple things which are far less complex =
using
iteration as by loops.
As an example creating a hex string on stream.
void ToHex(ostream &rstr, unsigned int n)
{
const char *HexChars =3D "0123456789ABCDEF";
if (n >=3D 16)
{
ToHex(rstr, n/16);
ToHex(rstr, n%16);
}
else
{
rstr << HexChars[n];
}
}
Jaap=20
|
|
From: Igor P. <igo...@po...> - 2003-02-14 15:43:25
|
Hi,
The most important thing about recursion is the fact that
it is equivalent to using a stack - so if someone is using
recursive functions then he is using OS stack - otherwise
he is using a dedicated stack (an array for example).
Which approach to choose depends on the actual
problem that needs to be solved - usually dedicated
stack is faster but the solution is less readable and requires
much more coding.
Best regards
Igor Pierscinski
-----Original Message-----
From: Louis Godio [mailto:lg...@ya...]
Sent: Friday, February 14, 2003 3:57 PM
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);=20
is easily implemented as either a simple loop or recursion;
BUT could you guys comment on stack space, run-time etc. for a call=20
like factorial(100) implemented as a recursion compared to a loop ?=20
--- Ioannis Vranos <no...@ho...> wrote:
> -------Original Message-------
> =20
> From: Per Westermark
> Date: =D0=E1n=E1=F3eloT, 14 =D6l=E2ndo=DCn=E9dn 2003 2:38:47 ee
> To: Jaap de Wolff
> Cc: dev...@li...
> Subject: RE: [Dev-C++] recursion
> =20
> I think you got a bit confused about terminology.
>=20
> Looping and iteration is actually the same thing.
>=20
>=20
> =3D=3D> Yes you are right.
>=20
>=20
>=20
> However, recursion is not anything that should be specifically =
avoided.
> It's a question of what problem to solve.
>=20
> 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.
>=20
> 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.
>=20
> Use recursion when recursion results in faster run-time, or an easier
> implementation. In other cases, select an iterative approach.
>=20
>=20
> =3D=3D> 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".
>=20
>=20
>=20
> 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
>=20
>=20
> =3D=3D> The "faster" thing is tough to prove. I agree with the =
"easier".
>=20
>=20
>=20
> Ioannis Vranos
>=20
> * Programming pages: http://www.noicys.freeurl.com
> * Alternative URL: http://run.to/noicys=20
__________________________________________________
Do you Yahoo!?
Yahoo! Shopping - Send Flowers for Valentine's Day
http://shopping.yahoo.com
-------------------------------------------------------
This SF.NET email is sponsored by: FREE SSL Guide from Thawte
are you planning your Web Server Security? Click here to get a FREE
Thawte SSL guide and find the answers to all your SSL security issues.
http://ads.sourceforge.net/cgi-bin/redirect.pl?thaw0026en
_______________________________________________
Dev-cpp-users mailing list
Dev...@li...
TO UNSUBSCRIBE: http://www.noicys.cjb.net/devcpp/ub.htm
https://lists.sourceforge.net/lists/listinfo/dev-cpp-users
|
|
From: Per W. <pw...@ia...> - 2003-02-14 12:37:40
|
I think you got a bit confused about terminology.
Looping and iteration is actually the same thing.
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.
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
/Per W
On Fri, 14 Feb 2003, Jaap de Wolff wrote:
>
>
> > -----Original Message-----
> > From: Ioannis Vranos [mailto:no...@ho...]
> > Sent: Friday, February 14, 2003 07:25 AM
> > To: dev...@li...
> > Subject: Re: [Dev-C++] recursion
> >
> >
> > -------Original Message-------
> >
> > From: Santiago
> > Date: =D0=E1=F1=E1=F3=EA=E5=F5=DE, 14 =D6=E5=E2=F1=EF=F5=DC=F1=E9=EF=F2=
2003 5:53:20 =F0=EC
> > To: dev-cpp-users-list
> > Subject: [Dev-C++] recursion
> >
> > Hello all,
> > Simple one: how often, critical, and necessary is the usage
> > of C++ recursion
> > in the "real world" programming field?
> >
> >
> > =3D=3D> It has its uses, but try to avoid using it. Use loops
> > instead (usually
> > iteration).
> >
> >
> >
> > Ioannis Vranos
>
> Iteration is usefull when you have to make more of the same (iterative)
> operations on the result of itself, before you have your result.
> A traditional example of anything which can't be solved without iteration=
is
> the resolving of a regular expression.
> But of course there are more simple things which are far less complex usi=
ng
> iteration as by loops.
> As an example creating a hex string on stream.
>
> void ToHex(ostream &rstr, unsigned int n)
> {
> =09const char *HexChars =3D "0123456789ABCDEF";
> =09if (n >=3D 16)
> =09{
> =09=09ToHex(rstr, n/16);
> =09=09ToHex(rstr, n%16);
> =09}
> =09else
> =09{
> =09=09rstr << HexChars[n];
> =09}
> }
>
> Jaap
>
>
> -------------------------------------------------------
> This SF.NET email is sponsored by: FREE SSL Guide from Thawte
> are you planning your Web Server Security? Click here to get a FREE
> Thawte SSL guide and find the answers to all your SSL security issues.
> http://ads.sourceforge.net/cgi-bin/redirect.pl?thaw0026en
> _______________________________________________
> Dev-cpp-users mailing list
> Dev...@li...
> TO UNSUBSCRIBE: http://www.noicys.cjb.net/devcpp/ub.htm
> https://lists.sourceforge.net/lists/listinfo/dev-cpp-users
>
|
|
From: Ioannis V. <no...@ho...> - 2003-02-14 13:20:52
|
-------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 2:38:47 =EC=EC=0D To: Jaap de Wolff=0D Cc: dev...@li...=0D Subject: RE: [Dev-C++] recursion=0D =0D I think you got a bit confused about terminology.=0D =0D Looping and iteration is actually the same thing.=0D =0D =0D =3D=3D> Yes you are right.=0D =0D =0D =0D However, recursion is not anything that should be specifically avoided.=0D It's a question of what problem to solve.=0D =0D The trivial example of the faculty function seems to be the most quoted=0D example for the use of a loop instead of recursion, but the example is=0D quite bad, since it's faculty is easier to implement and runds faster as = a=0D loop.=0D =0D There are matematical rules that makes it possible to rewrite any=0D iterative function into a recursive function. And in the same way, any=0D recursive function may be converted to use state queues to store the=0D recursive state.=0D =0D Use recursion when recursion results in faster run-time, or an easier=0D implementation. In other cases, select an iterative approach.=0D =0D =0D =3D=3D> 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".=0D =0D =0D =0D Examples where recursion faster and/or easier:=0D - light-tree evaluation in a ray tracer.=0D - parsing of mathematical expressions=0D - some recursively defined functions, such as Ackerman=0D - regular expression pattern matching=0D =0D =0D =3D=3D> The "faster" thing is tough to prove. I agree with the "easier".=0D =0D =0D =0D Ioannis Vranos=0D =0D * Programming pages: http://www.noicys.freeurl.com=0D * Alternative URL: http://run.to/noicys=20 |
|
From: Louis G. <lg...@ya...> - 2003-02-14 14:57:27
|
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
|
|
From: Per W. <pw...@ia...> - 2003-02-14 15:27:16
|
The factorial is faster and more efficient as a loop. In a loop, it may use the input parameter as loop variable, and only need a temporary for evaluating the product. A recursive solution would duplicate the input parameter and a temporary and a return address for each step of the algorithm. That's why faculty is so bad an example when comparing the two solution methods. While the mathematical definition of the faculty function is recursive, the actual problem isn't recursive in nature. /Per W On Fri, 14 Feb 2003, Louis Godio wrote: > 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 ? > > --- Ioannis Vranos <no...@ho...> wrote: > > -------Original Message------- > > > > From: Per Westermark > > Date: =D0=E1=F1=E1=F3=EA=E5=F5=DE, 14 =D6=E5=E2=F1=EF=F5=DC=F1=E9=EF=F2= 2003 2:38:47 =EC=EC > > 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. > > > > > > =3D=3D> 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 a= s > > 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. > > > > > > =3D=3D> Recursion resulting to faster run-time is something close to th= e > > 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 > > > > > > =3D=3D> The "faster" thing is tough to prove. I agree with the "easier"= =2E > > > > > > > > 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 > > > ------------------------------------------------------- > This SF.NET email is sponsored by: FREE SSL Guide from Thawte > are you planning your Web Server Security? Click here to get a FREE > Thawte SSL guide and find the answers to all your SSL security issues. > http://ads.sourceforge.net/cgi-bin/redirect.pl?thaw0026en > _______________________________________________ > Dev-cpp-users mailing list > Dev...@li... > TO UNSUBSCRIBE: http://www.noicys.cjb.net/devcpp/ub.htm > https://lists.sourceforge.net/lists/listinfo/dev-cpp-users > |
|
From: Ioannis V. <no...@ho...> - 2003-02-14 20:25:15
|
-------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 5:29:34 =EC=EC=0D To: Louis Godio=0D Cc: Ioannis Vranos; dev...@li...=0D Subject: RE: [Dev-C++] recursion=0D =0D The factorial is faster and more efficient as a loop.=0D =0D In a loop, it may use the input parameter as loop variable, and only need= =0D a temporary for evaluating the product.=0D =0D A recursive solution would duplicate the input parameter and a temporary=0D and a return address for each step of the algorithm.=0D =0D That's why faculty is so bad an example when comparing the two solution=0D methods. While the mathematical definition of the faculty function is=0D recursive, the actual problem isn't recursive in nature.=0D =0D =0D =0D =3D=3D> For generic algorithms a recursive solution is always more defici= ent than the iterative solution. =0D =0D In space because every call has its own instances of the local variables = and also in most cases all the continuous function calls are stored in the st= ack =0D =0D In run-time because of the function calls.=0D =0D =0D Ioannis Vranos=0D =0D * Programming pages: http://www.noicys.freeurl.com=0D * Alternative URL: http://run.to/noicys=20 |
|
From: Per W. <pw...@ia...> - 2003-02-14 20:41:59
|
EMA System email: pw...@ia... Per Westermark web: http://iapetus.neab.net Vargvaegen 174B phone: +46 8 410 17 198 S-906 42 Umeaa Sweden On Fri, 14 Feb 2003, Ioannis Vranos wrote: > -------Original Message------- > > From: Per Westermark > Date: =D0=E1=F1=E1=F3=EA=E5=F5=DE, 14 =D6=E5=E2=F1=EF=F5=DC=F1=E9=EF=F2 2= 003 5:29:34 =EC=EC > To: Louis Godio > Cc: Ioannis Vranos; dev...@li... > Subject: RE: [Dev-C++] recursion > > The factorial is faster and more efficient as a loop. > > In a loop, it may use the input parameter as loop variable, and only need > a temporary for evaluating the product. > > A recursive solution would duplicate the input parameter and a temporary > and a return address for each step of the algorithm. > > That's why faculty is so bad an example when comparing the two solution > methods. While the mathematical definition of the faculty function is > recursive, the actual problem isn't recursive in nature. > > > > =3D=3D> For generic algorithms a recursive solution is always more defici= ent ------For some SIMPLE algorithms, loops may always win. > than the iterative solution. > > In space because every call has its own instances of the local variables = and > also in most cases all the continuous function calls are stored in the st= ack Shared variables area easily stored in a global struct, or in an object. The needed state variables must be kept for a loop solution too, in this case in a queue. > > > In run-time because of the function calls. function call has to be matched against queue push/pop for software-assisted state stack. > > > Ioannis Vranos > > * Programming pages: http://www.noicys.freeurl.com > * Alternative URL: http://run.to/noicys |
|
From: Ioannis V. <no...@ho...> - 2003-02-14 20:16:53
|
-------Original Message-------=0D =0D From: Louis Godio=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 4:57:27 =EC=EC=0D To: Ioannis Vranos; dev...@li...=0D Cc: dev...@li...=0D Subject: RE: [Dev-C++] recursion=0D =0D Greets,=0D Both of your comments raise interesting questions regarding how to=0D construct efficient run-time code. The simple recursion=0D factorial(n)=3D n(n-1)..(1); =0D is easily implemented as either a simple loop or recursion;=0D BUT could you guys comment on stack space, run-time etc. for a call =0D like factorial(100) implemented as a recursion compared to a loop ? =0D =0D =0D =3D=3D> Of course. Recursion is very much run-time/space deficient in com= parison to loop.=0D =0D =0D =0D Ioannis Vranos=0D =0D * Programming pages: http://www.noicys.freeurl.com=0D * Alternative URL: http://run.to/noicys=20 |
|
From: Per W. <pw...@ia...> - 2003-02-14 20:36:56
|
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 |
|
From: Ioannis V. <no...@ho...> - 2003-02-14 20:48:12
|
-------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 |
|
From: <tel...@ya...> - 2003-02-15 14:18:27
|
the thing with factorials is, that it's recursively horrible since the numbers get very big very quicky, ie the space allocation required will be massive. before you even hit 13! or factorial(13) you exceed the limit for the max value for integers. (2,147,483,647) ( http://www.newdream.net/~sage/old/numbers/fact.htm ) of course you could then use floats or double data types etc, but the thing is, iteratively, the space is set aside perhaps once for the factorial, one counter, and once for the answer. e.g. int factorial; int answer=1; int i=0; /*assign factorials, cater for 0!=1 exception */ while (i<factorial) { answer=answer*(factorial-i); i++; } /* then cout or printf or fstream of whatever u want to do with it.. */ recursively however, as mentioned, it works through stack, thing is, each stack level is sorta like the 'run time embodiement' of the called function. sorry, not too good @ this yet... :( basic thing i'm getting @ is, each time the recursed function is called, then the data is passed as it would to any other function, and passing all that data around is obviously gonna be a detriment to performance as has been mentioned. there are things that work better recursively, one example is euclid's agorithm. google search it if u have to, altho i assume most of you would know what it is. last thing, i cant think of an example, but i think any recursion can be handled with a loop, but not all loops can be done via recursion... i dunno, how was i?? please lemme know if i dont know jack :P http://mobile.yahoo.com.au - Yahoo! Mobile - Exchange IMs with Messenger friends on your Telstra or Vodafone mobile phone. |
|
From: Per W. <pw...@ia...> - 2003-02-14 15:23:15
|
The speed issue is a question of locality of reference, and of knowing the state changes needed to reach a specific state. A recursive algorithm may often know exactly how it came to a specific state, while an iterative algorithm have to pop a state entry from it's queue and then perform some if tests or a switch statement etc to decide how to continue. In a recursive solution, the hardware i.e. the CPU will perform the stack allocation/deallocation and on most modern processors grow the stack when needed. In an interative solution, the manually used queue must either be of fixed size, or perform malloc/free (new/delete) for each state change. Which solution is better has to be decided for each individual problem. /Per W On Fri, 14 Feb 2003, Ioannis Vranos wrote: > -------Original Message------- > > From: Per Westermark > Date: =D0=E1=F1=E1=F3=EA=E5=F5=DE, 14 =D6=E5=E2=F1=EF=F5=DC=F1=E9=EF=F2 2= 003 2:38:47 =EC=EC > 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. > > > =3D=3D> 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. > > > =3D=3D> 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 > > > =3D=3D> 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 |
