Recursion

Q. What is recursion and why we use it?

Ans. As the name suggest recursion is to call something or do something again and again.

In programming language if a function invokes itself or in lay man language a function call itself. Then this programming paradigm is called recursion.

Recursion is very useful in some situations.  Like: finding the factorial.

But every coin has two faces. So Recursion also has some cons.

Ex:

int find_fact(int k){

       if(k==0 || k==1)

             return 1;

       else 

             return  k* finf_fact(k-1);

}

In this function we call find_fact again till we reach the termination condition which is k==1.

Before writing any recursive function we should think of what will be its terminating condition. Our calls to the same function should converge to termination point . It should not deviate away from the termination point otherwise it may go in to infinite loop.

Ex. 

if in above example I write k+1 instead of k-1 and if user send 2 as input to function then this will never going to be terminated. Because it is going away from the termination point. Recursive call should be converging to the termination point.

Any recursive function or program can be written without recursion but not other way around.

In recursive function in built stack of computer is used. It keeps all the information of the call at which line function is invoked. It puts that function frame to the top of the stack and then function returns it reach to the last address where it left the function and start evaluating again.

But as the number of calls increases the stack size increases. So for large number of inputs there might be segmentation fault due to stack overflow. So avoid the writing functions using recursion . Try to write it without recursion and use your stack so you know what is the size of the stack. Whether it is overflowing or not.

To find the complexity of the recursive function we write the recursive equation and try to solve it using Master's theorem or tree method or induction any of these or any other method.

Ex. the recursive equation of the above function is

               

T(n) = T(n-1) + C;                       

C is here some constant it may be zero or anything. It depends on the function. Here No loops in the function only just a condition and a multiplication expression so C's value here is turn to be 1.

By solving this you can get the complexity. I am leaving this is an easy exercise to do on your own.