RE: [Dev-C++] recursion

[Igor P. <igo...@po...>]

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