Thread: efficiency question

There is no single correct answer. It depends on the problem your code is written to solve.

Recursion works well when the depth is limited and you don't anticipate exceptions, and recursive solutions can be much cleaner (code wise) than iterative solutions (less code, fewer conditions). On the other hand, the use of recursion prevents some advanced compiler optimizations from recognizing execution patterns and subtle side effects that might produce more efficient code, and if the depth of the recursion goes too deep, you can start getting page faults on the stack. It is very difficult to parallelize (is that a real word?) a recursive algorithm, which prevents some optimizations available on some architectures.

Iteration has the advantage of lower call stack overhead at the expense of more complex control structures within the code. Depending on the problem definition and the nature of the recursion required by the algorithm, the data and control structures required to track the state of the processing may introduce too much complexity, and you may lose the advantages of an iterative technique.

It is up to the programmer to make a choice of algorithms based on the problem definition and the runtime constraints.

generally recursion is not good solution...but if u show ur code then we might be able to say precisely in ur case

I never use function recursion because it consumes more processing time and resources (the stack) and there is a risk that the stack is blown. Its an abuse in the art of programming a computer to use function recursion, it should have been prohibited in serious programming languages such as C and its dialects.
Profylaxis defense: Some people has claimed they use function recursion when they can be 100% sure it will not blow the stack. OK so it may work on that particular system, then, lets move that code to another processor, a PIC is an evil choice here because it has only a stack level of 8 function calls, and you no longer can be 100% sure it will not blow the stack. Learning how to do iteration rather than recursion appears to my mind as not any more difficult to grasp, so I see no argument there either and even if it is harder to learn I still see no argument in using function recursion. Therefore I recomend to you and everybody else to use iteration. And ask yourself this: What methode would the system designers of programs used in space shuttles, and medical equipment use, in the choice of function recursion or iteration? What would game designers chose? Or what do you think we will find in top-chess programs?

Originally Posted by fischerandom

Its an abuse in the art of programming a computer to use function recursion, it should have been prohibited in serious programming languages such as C and its dialects.

This looks like the foundation of a religious war. When I was in school, recursion was taught as a preferred technique. Of course, that was 25 years ago.

There are times when I use function recursion in embedded real-time code. Generally, there is a maximum depth on that recursion of 2. You have to, as I said in my previous post, take the run-time environment when choosing the algorithm.

Keep in mind that functional languages use recursion for "everything". Keep also in mind that sometimes finding the iterative algorithm is very difficult.