Recursion vs Efficiency

Before analyzing efficiencies of Recursive and Non-Recursive algorithms of same complexity we have to define what are Recursive and Non-Recursive Algorithms.

We can define recursive algorithm as an algorithm which calls itself with "smaller (or simpler)" input values, and which obtains the result for the current input by applying simple operations to the returned value for the smaller (or simpler) input. More generally if a problem can be solved utilizing solutions to smaller versions of the same problem, and the smaller versions reduce to easily solvable cases, then one can use a recursive algorithm to solve that problem.

We can define non-recursive algorithm as an algorithm which is executed only once to solve the given problem.

As an example following algorithms compute factorial of a given number in recursive manner and non-recursive manner respectively (Written C Language).

unsigned int factorial(unsigned int n) {
 if (n <= 1) return 1;

 return n * factorial(n-1);
}

unsigned int factorial(unsigned int n) {
 unsigned int result = 1;
 if (n <= 1) return 1;
 while (n--) result *= n; 

 return result;
}

Recursive algorithms are somewhat less efficient than non-recursive algorithms with same theoretical complexity because of the nature of recursive algorithms discussed above.

Lets take above factorial example to analyze this situation:

When using recursion to find the factorial of given number each call itself does not provide the solution to original problem. Instead the recursive call provides a partial solution that must be multiplied by a number to get the final result. If you consider operating stack of the OS, each recursive call must be kept on the stack because each call is incomplete until the next call above on the stack is returned. When considering factorial for 15, factorial(15) goes on the stack and stays there until factorial(14) returns. factorial(14) goes above the factorial(15) on the stack and stays there until factorial(13)returns, etc.

So, recursive computation involving n recursive function calls would require, therefore, space linear in n. On the other hand, an iterative program typically uses only constant amount of memory, independent of the number of iterations.

Also In the case of recursive algorithms, they have some problems with compiler optimizations. For example, Jon Bentley [http://dns.uls.cl/~mramos/libro/books/book10/9806m/9806m.htm] has found that a functionally identical recursive method optimized by the C compiler if he did not use ?: conditional operator. However it did not optimize function if he use conditional operator ?:. He also found that recursion can be very expensive, taking up to 20 times longer for some operations that are naturally iterative. Above url mentioned contain more details about his experiments.