## Recursion in C

### What is Recursion?

Recursion is the process in which a function calls itself directly or indirectly. And the function that calls itself is known as a recursive function.

### How recursion works?

Basic Structure of Recursion :
``````
void recursion()
{
recursion();
}
void main()
{
recursion();
}
``````

We all know that a C program terminates from main( ) function, similarly here main( ) function calls the recursion( ) function in very first step and then the recursion( ) function calls itself again. All kind of Recursion functions works in this similar way.

### A Recursion Program :

``````
//c program to calculate
//sum of natural numbers recursively

#include<stdio.h>

int sum(int n)
{
if (n != 0)
return n + sum(n-1);		// sum() function calls itself
else
return n;
}

int main()
{
int num, result;

printf("Enter a positive integer : ");
scanf("%d", &num);

result = sum(num);		//sum() function is called by main() function

printf("Sum of first %d numbers = %d",num, result);
return 0;
}
``````

### Direct & Indirect Recursion :

##### Direct Recursion ~
A function is called direct recursive if it calls the same function itself.
``````
void directFunction()
{
directFunction();
}
``````
##### Indirect Recursion ~
A function is called indirect recursive function if it calls another and the called function calls the previous function directly or indirectly.
``````
void indirectFunction1()
{
indirectFunction2();
}

void indirectFunction2()
{
indirectFunction1();
}
``````

### Key Points about Recursion :

• ~ While using recursion in a function, programmers need to be careful to define an exit condition from the function, otherwise it will go into an infinite loop.
• ~ Recursive program takes more space than usual iterative programs.
• ~ Recursive program takes much time as it calls function many times and returns the value.