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.

main() function called inside main() definition --- C Language

Many think that when the main() function call inside the main(), recursion goes on infinite times. But it is not true as such. It is always  important to know how function calling and recursion works. The function calls work with the help of a stack by PUSHing all the functions to a stack and POPing the functions from the stack when they are executed. The following figure gives the complete picture of this working. When a function "func1()" is called from within the "main()" method, the "func1()" is PUSHed onto the stack. Similar is the case with the function "func2()". When the function "func2()" gets completed, it is POPed from the stack. The function calls take place until the stack overflow occurs, that is until the stack is completely filled with the functions. This implies that the recursion without a suitable condition takes place not infinite times but stack size times.

   

This particular experiment when conducted, compiles successfully but it suffers from a run time error.

Lets have a look at the functionality of this entire concept and thus decide the output of the program. We also experiment on the number of times the function is called. The entire simulation is with the help of a simple program as given below:

#include "stdio.h"

int i=0;

int main()

{

            i++;

            printf(" %d\n",i);

            main();           /* Call main() inside main() */

            return 0;

}

Now,in the above program the value of "i" signifies the number of times the function is called.

First, I considered running this program on Turbo C on Windows platform, where the size of a variable of type "int" is 2 bytes. When I ran this program, the function got called around 15000 times and then the compiler crashed with the error message in the image shown below:

The next time I tried the same program on GNU C compiler on Ubuntu 10.04, where the size of a variable of type "int" is 4 bytes. Now when the program is compiled, it returned successful compilation.

But when it is run, a runtime error was issued as "Segmentation fault". The error message in the dialog box for Turbo C also indicated the same thing.

Now what is this segmentation fault? It is an error that occurs when a program attempts to access a memory location that it is not allowed to access, or attempts to access a memory location in a way that is not allowed. It occurred in this case due to the stack overflow. So, main() called inside main() gives segmentation fault.

The number of times the function call took place varies continuously between two executions of the program. In Turbo C, the number of times the function call took place is around 16000 while in GNU C Compiler, this figure is around 327000.