Algorithm design --- Iteration, Recursion or Tail recursion

The best method for solving a problem has to be chosen under many circumstances. Techniques such as Greedy method, divide and conquer method, dynamic programming etc., are used to solve the problems under different constraints.

In some cases, the method followed to solve a problem might be easy to program but might not deliver good performance due to more space and time complexities; Recursion is one such example. Recursion is a master technique to solve many complicated problems, but the space and time complexity are higher than those in the conventional program without having the recursion. It is trouble using recursion as there is no portable way to tell how deep recursion can go without causing trouble (how much 'stack space' the machine has), and there is no way to recover from too-deep recursion (a 'stack overflow'). Recursion requires more number of steps to solve a problem.

Iteration can do things faster for us. However, in some problems, using iteration becomes too cumbersome and tedious to be applied especially when the problem is naturally recursive. Thus, the time taken for designing the algorithm and the efficiency of the algorithm must be taken into consideration while devising a method to solve a problem.

If iteration is getting complicated, then you always have the weapon of TAIL RECURSION. With Tail recursion you can get the advantages of recursion while overcoming the defects in the iteration method. Tail recursion is a process of using the function call as the last executed statement in the function definition. Here, we take the return value as one parameter of function itself. We use stack to maintain all the functions but here it will not append new function in stack but it will overwrite the value of previous function with the current one. Thus, the function call time and stack implementation time will be reduced giving better performance.

Let us solve the problem of finding factorial of a number using these three methods:

CASE 1: Using Iteration:

int factorial ( int no){

         int i, fact=1;

         for (i=no; i>1; i--)

                fact=fact*i;

         return fact;

}

CASE 2: Using Recursion:

int factorial ( int no) {

        int fact=1;

        if (no > 1)

               fact=no * factorial (no - 1);

        return fact;

}

This process is implemented in stack as-

CASE 3: Using Tail Recursion:

int factorial ( int n, int fact)

{

             if ( n==1 )

                    return fact;

             else

                    factorial ( n-1, n*fact);

}

This will be implemented in stack as-

Here, the tail recursion takes only 4 steps for getting factorial of number 4. It reduces both space and time and improves the performance.

References: "Data Structures Through C" By S.K. Srivastava.