hi everyone. Often we have two possibilities for getting a task done: we do it by looping or we can do it by writing a recursive function. About efficience, what is the best way?
hi everyone. Often we have two possibilities for getting a task done: we do it by looping or we can do it by writing a recursive function. About efficience, what is the best way?
Use a loop since recursion would impose the overhead of having to save the current state, and consequently there is typically some maximum limit to the number of levels of recursion that could reasonably be reached.
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
You should prefer loops by default, but there are exceptions:
* The problem domain is naturally recursive and not deep -- for instance, game tree search
* The iterative version would be extremely hard to write
* The iterative version would be extremely hard to understand.
Unless you have one of these cases, use a loop.
Thanks for your answers. Do you know any tutorial about C efficience in wich issues like this are covered?
Not aware of any tutorial, but you should be aware that the compiler is nearly always good at optimizing loops. It will only sometimes make sense out of recursive algorithms (real simple cases can usually be turned into loops anyways).
If the compiler can't make the recursion into a plain loop, then it's almost certainly at the very least two instructions [the call that takes you to the next level of recursion, and the return to get back again] longer (thus slower) to use recursion [exceptions do exist - and I can't think of any example where those are not also in the "exceptions" listed by Brewbuck].
Further, deep recursion, or recursion with lots of state on the stack [large local variables] is inherently dangerous, since the running out of stack is "catastrophic" - so you need some way to prevent overflwoing the stack, by knowing that you will never recurse more than x levels.
--
Mats
Compilers can produce warnings - make the compiler programmers happy: Use them!
Please don't PM me for help - and no, I don't do help over instant messengers.