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?
Printable View
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.
Typically prefer recursion if you can't do it in any efficient way through iteration.
You should prefer loops by default, but there are exceptions:Quote:
Originally Posted by mariano_donati
* 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).Quote:
Originally Posted by mariano_donati
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