Recursion

Suppose you are standing in a queue and you want to know the number of people standing in the queue. You cannot directly count the number of persons but if you the number of people standing in front of you then you know that The total number of people in the queue = The number of people ahead you + 1 (including you). But how will you know the number of people ahead you ? You can ask the person standing ahead you. That person also doesn't know the number of person ahead him so he asks the person in front of him and so on. The queue has limited persons so when the second person asks the first person that how many people are ahead you, then the first person says 0. Now, the first person has given his answer to the second person. So, the second person replies to the third person by saying that there are (0+1) persons standing in front of him (by including the first person). The third person replies to the fourth person by saying there are (1+1) two persons in front of him (ny including the second person) and so on till the last person.
Real life example of recursion
The process happening above is known as recursion. No person standing in the queue knows the answer expect the first one. So,they ask the person in front of them add 1 to it and get their own answer. Here, the answer of one of them is dependent on the other. When one person does not know the answer, he asks the person on his front and so on. When one person knows the answer, he gives it to the person behind him and so on until the final answer is obtained. The thing to remember here is that there is atleast one person who knows the answer. If nobody knows the answer, then the problem cannot be solved.

What is recursion ?

In programming terms, the process in which a function which calls itself again and again is called as recursion. The problem is divided into subproblems until the answer to the subproblem is known. After that, we keep merging the solution of the subproblems to get the final answer.
For example -
                
    #include<stdio.h>

    void count_persons(person p)
    {
       if(there is no one standing in front of p)                               // Base condition
         return 0 ;
       
         else
          {
            return 1 + count_persons(the person standing in front of p) ;       // Recursive call
          }
    }

    void main()  {
     
        cout<<count_persons(the last person standing in the queue) ;
    }
A recursive function must have a base condition i.e a subproblem whose solution is already known. Without a base condition, the problem will keep on dividing and dividing but no solution could be found. The program would be struck in an infinite loop. Hence, the base condition must be defined clearly.

Example #1

Suppose you want to calculate the factorial of a number. We all know that : n ! = n x (n-1) ! i.e if we know the value of (n-1) ! , we can compute n ! by multiplying n to it.
Lets see how we can do it in the recursive way - 
        
    #include <iostream.h>
    int fact(int n)
    {
        if(n <= 1)                   // Base Condition
        return 1 ; 

        else
        return n * fact(n-1) ;      // Recursive Call
    }
    void main()
    {
      int n;
      cout<<"Enter a number : ";
      cin>>n;
      cout<<"Factorial of "<<n<<" = "<<fact(n);

    }

Output

        
    Enter a number : 10
    Factorial of 6 = 720
The whole code can be understood by seeing this -

6 ! = 6 x fact(5)
6 ! = 6 x 5 x fact(4)
6 ! = 6 x 5 x 4 x fact(3)
6 ! = 6 x 5 x 4 x 3 x fact(2)
6 ! = 6 x 5 x 4 x 3 x 2 x fact(1)
6 ! = 6 x 5 x 4 x 3 x 2 x 1
6 ! = 6 x 5 x 4 x 3 x 2
6 ! = 6 x 5 x 4 x 6
6 ! = 6 x 5 x 24
6 ! = 6 x 120
6 ! = 720

Example #2

Suppose you want to calculate the sum of numbers from 1 to n. We know that the Sum of numbers from 1 to n = Sum of numbers from 1 to (n-1) + n.
Let's see how we can do it the recursive way.
      
    #include <iostream.h>
    int sum(int n)
    {
        if(n == 1)              // Base condition
        return 1;
        else
        return sum(n-1)+ n ;    // Recursive call
    }
    void main()
    {   
     int n ;
     cout<<"Enter the value of n" ;
     cin>>n ;
     cout<<"Sum of numbers from 1 to n = "<<sum(n) ;
    }

Output

        
    Enter the value of n : 5
    Sum of numbers from 1 to n = 15
The whole code can be understood by seeing this -

Sum(5)=Sum(4)+5
Sum(5)=Sum(3)+4+5
Sum(5)=Sum(2)+3+4+5
Sum(5)=Sum(1)+2+3+4+5
Sum(5)=1+2+3+4+5
Sum(5)=3+3+4+5
Sum(5)=6+4+5
Sum(5)=10+5
Sum(5)=15

Advantages and Disadvantages

Advantages of recursion are -

  1. It is easy to write and understand.
  2. Makes code shorter.

Disadvantages of recursion are -

  1. Takes additional stack space.
  2. Makes code difficult to debug.