On Jan 5, 9:19 pm, Salt_Peter <pj_h...@yahoo.comwrote:
Quote:
On Jan 5, 2:17 pm, "athar.mir...@gmail.com"
<athar.mir...@gmail.comwrote:
Quote:
As the English word suggests: a recursion is simply a function
that calls itself. Which is neither efficient nor beneficial.
It's beneficial when its beneficial. On most modern
architectures, it's often as efficient as the alternatives. (I
once benchmarked a recursive version of quick sort, and one
which avoided recursion. the recursive version was faster.)
Quote:
Each call generates a new local stack which eventually all
need to be unwound. So in C++, its usually replaced with
better alternatives. An example of a preferred alternative
would then be a function object (functor).
How is that relevant to recursion. A functional object is still
a function, and can still be recursive or not, according to how
you write it.
Quote:
Recursive functions have no state (what does that mean?).
I don't know? I have no idea what you're trying to say there.
Quote:
To give you an example of recursion: (that incidentally
doesn't do what you'ld expect)
Quote:
#include <iostream>
Quote:
void recursion(int n)
{
std::cout << "n = ";
std::cout << n << std::endl;
if(n < 10)
recursion(++n);
}
Quote:
int main()
{
recursion(0); // prints 11 times
}
And your point is?
Any iterative algorithm can be rewritten to use recursion. Some
languages don't even have looping constructions, but in C++,
using recursion to simluate iteration is poor programming
practice. On the other hand, recursion is considerably more
powerful than iteration, and not all recursive algorithms can be
rewritten in terms of pure iteration, unless you introduce a
manually managed stack, which is a lot more work for the
programmer, and typically less efficient in terms of run-time.
How would you do a depth first visit of a tree without
recursion, for example? (Or quick sort, for that matter? The
standard non-recursive iteration requires a user managed stack.)
Note that recursion is typically less efficient in terms of
memory than managing the stack yourself, so you'll normally want
to avoid recursing too deeply.
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
