Recursion

  • Recursion is the process in which , function calls or invoke itself repeatedly untill certain condition is met.
  • Calls itself means ,in the body of function where we are defining a function, a call has given to the same function in that function body itself.
  • This process is used in iterative type of problems.
  • Recursion is used in Iterative computation where each action is stated in terms of previous result.
  • Solving problem Using Recursion reduce the lines of code.
  • Complex programs can be written very easily by recursion.
  • They are easy to write but picking the logic is pretty much Difficult.
  • At every problem, you have to specify some condition ,so that iteration can stop.
  • Every problem which is solved with recursion ,that same problem can done with loops.
  • But problem which is solved with loops that may not done with recursion.
We will write simple program for sum of n numbers with recursion.

Solution:
#include<stdio.h>

int sum(int n); //declaration

//definition
int sum(int n)
{
    if(n == 1) //if n will be equal to 1, then the iteration will stop,
        return 1;   //and it will return 1.
    else
        return(n + sum(n-1) );//function calling it's self.
}

Using Above defined function:
void main()
{ 
int result;
  //calling function 'sum'.
result = sum(5);
printf("\nSum is %d",result);
}

Ouput:
Sum is 15.
  • As you saw, program was of few lines of code, but what was going on behind screen,let's understand it.
  • Step by Step Explanation.
  • step1:As function was call by passing 5 to it, As value at if block was checked and condition evaluated to false and control went to else block.
    step2:at there is return statement which is returning current value of n which is 5 plus with function 'sum' with parameter n-1 which is 4 now
  • step3: Now function is called by passing 4 to it, and if condition was checked and evaluated to false and control went to else block.
    step4: And again it returned current value of n which is 4 plus with function sum with parameter n-1 which is 3 now.
  • step5: Now function is called by passing 3 to it,and if condition was checked and evaluated to false and control went to else bloc k.
    step6: and again it returned current value of n which is 3 plus with function 'sum' with parameter n-1 which is 2 now.
  • step7: Now again function is called by passing 2 to it,and if condition was checked and evaluated to false and control went to else block.
    step8: And again it returned current value of n which is 2 plus with function 'sum' with parameter n-1 which is 1 now.
  • step9: Again function is called by passing 1 to it,and if condition was checked and now it evaluated to true and now it returned value 1,and as you know when function returns its value then control goes at that point where it was call ,now it will go to step no 7.
  • Now function call at step no:8 has returned value 1 So it will get add with 2 and it will become 3.
  • but 3 is a returned value for function which is called at step no:6.
    So ,returned value will be added with 3 and will become 3+3 = 6,now value has become 6.
  • But value '6' is returned value by function which is called at step no:4.
    So returned value will get added with 4 which will become 6+4=10,now value has become 10.
  • But Again value 10 is returned value for function which was called at step no:2.
    So returned value will get added with 5 which will become 10+5=15,now value has reached to 15.
  • As value 15 is returned value for function which is call at step no:1.
    Finally the the actual function has returned the value which is 15, And we have assigned that value to variable result, and that is are final Output.
  • Hence , Sum of first five number is 15.


  • As Recursion is an pretty much difficult topic as from the beginners point of view.
  • So, to understand it more better ,do more practice on it.
  • For getting good command on Recursion, do more practice on it.




Further Concepts:


People Also Searched: