To many ,the concept of recursion may seem very difficult to grasp at the first go.The prime reason being the way it is presented.Lets get our brain cells around it !

what exactly is recursion ?

Recursion is just a coding style or a technique in which we try to express a given problem in terms of itself. woah ! that statement is everywhere but what exactly does it mean when we try to solve a problem using a programming language? lets try to break it !

Lets consider that the problem we have at hand is: Find the sum of elements of an array.

We can easily deduce that sum of array is equal to :

First element + sum of the remaining elements of the array i.e

Here we get two parts: first element+ an array of rest of elements.now the second part itself is an array whose sum is again its first element +sum of the remaining elements of the array. and so on.

We can easily visualize that our original problem has been successfully expressed in terms of itself. and that is recursion. We will code this example later below but first lets take one more example to confirm we have actually understood the concept behind recursion.

(Problem 2) : find the factorial of a number.

We know :

5! = ( 5 X 4 X 3 X 2 X 1 ) =>( 5 ) X ( 4 X 3 X 2 X 1 ) =>( 5 ) X ( 4 ! )

we can see that in general n! = n X ( n - 1 ) !

Here also we can find that the problem of finding factorial can be expressed in terms of itself i.e: number X factorial(number-1)

what happens behind the scenes(in the memory) when a function calls itself?

To understand this the understanding of a very basic data structure ( STACK ) is required.The below diagram shows push () and pop() operation on the stack. In this addition(called as push)and deletion(called as pop)is performed only on the top of the stack.

consider the code below :

    Test(){
       Test();
}

Every time the function calls itself, a copy of it is created and pushed onto the stack and this keeps on going until the condition for breaking out of recursion is met or the stack memory is full. The below diagram depicts the status of stack in case of a recursive call of a function test(). Then the function instance from the top is executed and poped out until all instances are executed.

implementing Recursion in c++

Solution to( Problem 2) using recursion:

 #include<iostream>
 using namespace std;
    int factorial(int n);
    int main()
    {
        cout<<factorial(4);
        return 0;
    }
    int factorial(int n)
    {
        if(n!=1)
         return n*factorial(n-1);
    }

Note: Every recursive function should have a Base case which helps to break out of recursion.in the above program the base case is if (n!=1)

Solution to (problem 1) using recursion :

#include<iostream>
using namespace std;

int arr_sum( int arr[], int n )
{

    if (n < 0) {
         return 0;
    }

    return arr[n] + arr_sum(arr, --n);
}
int main() { 
     int arr[] = {1,2,3,4,5};
    int sum;
    sum = arr_sum(arr,4);
    printf("\nsum is:%d",sum);
    return 0;
};

Why do we need recursion?

Because it makes solution to the problem more intuitive to solve and understand .