Register Now

Login

Lost Password

Enter your email to reset your password.

BY Author

Recursion

When something is described in terms of itself, it is known as recursion.
Similarly, in C programming when a function is described in terms of itself, it is known as a recursive function.
Or simply we can say that the function that calls itself is known as recursive function & the process is known as recursion.

Example

 int main()
 {
     -------------
     -------------
       main();
     -------------
     -------------
 }

In the above example, the main() function is known as a recursive function because it is calling itself.
To prevent recursive function calling itself infinitely, we must be able to stop it at some specific point.
For that, we need to use some exit condition inside a function, so that function can stop calling itself at the required point.
We can make any user defined function as a recursive function.
The diagram showed below shows how recursive function calls itself.

C Programming Language Recursive Function Calling Itself

Recursion helps us to do the same thing that we can do using loops like for, while & do-while.

For the better understanding let’s take a small & simple example that adds the first 4 natural numbers, that is from 1 to 4.

Numbers from 1 to 4 can be added using loops as well as recursive function.

Example using for loop

#include <stdio.h>
int addition(int n);
int main()
{
    int add = addition(4);
    printf("\n Addition of first four natural numbers = %d",add);
    return 0;
}

int addition(int n)
{
    int i, sum=0;
    for(i=1;i<=n;i++)
    {
        sum = sum+i;
    }
    return sum;
}

Output

Addition of first four natural numbers = 10

Example using recursive function

#include <stdio.h>
int addition(int n);
int main()
{
    int add = addition(4);
    printf("\n Addition of first four natural numbers = %d",add);
    return 0;
}

int addition(int n)
{
    if(n==1) // exit condition
    {
        return 1;
    }
    return(n+addition(n-1));
}

Output

Addition of first four natural numbers = 10

Working of above recursive function

C Programming Language Recursion Working

In the above program addition() function calls itself. Therefore it is known as a recursive function.
Each time addition() function calls itself, a new addition() function is created in a stack memory.
That is addition() function with its new local variables is created in a stack memory as shown below:

C Programming Language Stack Memory Winding while Recursion

When one addition() function calls another addition() function, the local variables of previous addition() function are kept on hold & local variables of another addition() function become active.
When addition() function hits (executes) exit condition, it starts working in reverse direction.
Each time addition() function executes in reverse, a newly created addition() function is destroyed step by step from stack memory as shown below:

C Programming Language Stack Memory Unwinding while Recursion

In the above program, we have added numbers only from 1 to 4 through recursive function, just for the understanding purpose. Actually, we can add any number of natural numbers using the same recursive function as shown below:

Example

#include <stdio.h>
int addition(int n);
int main()
{
    long int add,num;
    printf("Enter range = ");
    scanf("%d",&num);
    add = addition(num);
    printf("\n Addition of first four natural numbers = %d",add);
    return 0;
}

int addition(int n)
{
    if(n==1)
    {
        return 1;
    }
    return(n+addition(n-1));
}

Output

Enter range = 10

Addition of first four natural numbers = 55

Advantage of Recursion

Recursion makes the program more elegant and easy to understand.

Disadvantages of Recursion

If recursion didn’t hit the exit condition, the function would execute infinitely, which will cause stack overflow & we will get stack overflow error.

Recursion uses more memory as compared to loops.

Recursion makes execution of program slow because it includes a lot of pushing & popping process in the stack.

 

Leave a reply