RE: [Dev-C++] recursion

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

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
>