Principle of Recursion

Recursion

An algorithm is said to be recursive if it solves a problem by reducing it into an instance of the same problem with smaller input. The function that calls itself is called the recursive function. Recursion is an alternative to iteration in making a function execute repeatedly.

eg: The recursive function/algorithm to compute factorial:

int fact (int n){

int x,y;

if (n==0)

return(1);

x = n - 1;

y = fact(x);

return(n*y);

}

Here, stack is used to keep the successive generations of local variables, the parameters and the returned values. This stack is maintained by the system (like the C system) and is invisible to the user.

Each time a recursive functions is entered, a new allocation of its variables is pushed on top of the stack. Any reference to local variable or parameter is made through the current TOS. When the function returns, the stack is popped, the top allocation is freed, and the previous allocation becomes the current stack top to be ued for referencing local variables.

Figure below shows the visualization of how fact(4) works. It shows the series of snapshots of the stacks fot the variables n, x and y as execution of the function processes:

* Each time the recursive routine returns, it returns to the point immediately following the point from which it was called.

Principles of Recursion

1. A recursive algorithm/function must have some way of stopping its recursion, else it will call itself forever
2. Some algorithms are mostly suited to a recursive solution, especially problems concerned with complex data structures such as trees.
3. Some algorithms only look as though they are ideally suited to recursion. But they turn out to be much less efficient than iterative solutions. Eg: times for factorial calculation: Recursive factorial: 478 ms. Iterative : 230 ms.
4. if a non-recursive version for a problem can be written which is only slightly larger than recursive version, then preferably use the non-recursive version.

Recursion vs Iteration

Recursion, of course, is an elegant programming technique, but not the best way to solve a problem, even if it is recursive in nature. So, if there exists equal complexity of iterative codes and recursive codes for the solution of a problem, then it is always recommended to use the iteration due to the following reasons:

1. Recursive method requires stack implementation
2. Recursion makes inefficient utilization of memory, as everytime a new recursive call is made, a new set of local variables is allocated to function.
3. It slows down the execution speed, as function call requlres jumps, and saving current state of program onto stack before jump.

References:

1. Y. Langsam, M. J. Augenstein and A. M Tenenbaum, “Data Structuresusing C and C++”

2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, “Introduction toAlgorithms”

3. G.W. Rowe, “Introduction to Data Structure and Algorithms with C andC++”