RE: [Dev-C++] recursion

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

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