# C Recursion

In this tutorial, you will learn about the recursive function. Recursive functions are the functions which will call themselves inside it. While using recursion programmers need to be careful in defining an exit condition from the function. If the programmer forgets to mention the exit condition then the program will go into infinite recursion. Recursive functions are very useful in solving many mathematical problems. For example, while calculating the factorial of a number, generating Fibonacci series etc.

## How does recursion works?

Following is the syntax of the recursive function.

void recursive_fun()
{
….
recursive_fun();

}
int main()
[

recursive_fun();
….
}
As illustrated above, the recursive function will have a function with the same name inside it. In this way, the same function is called again and again until the given condition is met.  This is to say that our function will execute the number of times in our program until it meets the base condition(stopping condition). Recursive functions are very useful, however, it is slower than iterative functions. Similarly, the recursive function also consumes more memory than iterative functions. Now go on through the examples given below to learn more about recursive function uses.

### C program to calculate factorial of a given number using recursion:

Here, you will see how we will calculate the factorial of a given number by using recursion. In general, the factorial of a number ‘x’ can be written as x! which can be written as:

n! = x(x-1)(x-2)…..2.1

In maths, a factorial is written as n! and is written as follows:

The factorial formula for n:

n! = n(n - 1)(n - 2) ... 2..1

After all, you can see that first we take an integer and keep multiplying the same integer by a number less than the previous number each time. For example, 4!= 4*3*2*1, which is equal to 24.  It is simple and easy to calculate the factorial of a small number. But in the context of large numbers, it is very difficult. For this reason, we will write code for it.

Code:

#include<stdio.h>
int factorial(int);//Fucntion protoype
int main()
{
int n,fact;
printf("Enter a number: ");
scanf("%d",&n);
fact=factorial(n);//Function call
printf("The factorial of the given number is: %d", fact);
}
int factorial(int x)//Fucntion definition
{
if(x<=1)
return 1;
else
return (x*factorial(x-1));//Recursive Fucntion
}

Output:

Enter a number: 5
The factorial of the given number is: 120
Analysis:
As illustrated in the code above, we will define a function with return type int. The function evaluates the factorial by calling itself numerous times until the value of the number becomes 1. In summary, we can say that the recursive function in the above program will help to evaluate the factorial of the given number by multiplying the number by every number below it using recursion.

### C Program to print the Fibonacci series up to n terms by using recursion:

In this section, you will learn how to calculate the Fibonacci series up to n terms by using recursion. Firstly, Fibonacci series is the series generated by adding previous two numbers in sequence. The numbers are in the following sequence.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……..

Therefore, you can see that every number generated later will depend on the previous numbers to generate a sequence. So we can appply the recursion easily here which makes our codes more readable. Now see the code below to see how it works.

Code:

#include<stdio.h>
int fibonacci(int);
int main()
{
int x,i,f;
printf("Enter how many numbers you want to generate. ");
scanf("%d", &x);
f=fibonacci(x);
printf("%d\t", f);
}
int fibonacci(int n)
{
if(n==0){
return 0;
}
if(n==1)
{
return 1;
}
else{
return (fibonacci(n-1)+fibonacci(n-2));//Recursion Function
}
}

Output:

Enter how many numbers you want to generate. 9
34

Analysis:

In the program above, we have generated a Fibonacci series by using recursion. The use of recursion has enabled the understanding and readability of the program. Recursive functions are powerful but it is important to realize that we must not forget to put the stopping condition. Otherwise, the program won’t stop which may also lead to the crashing of the system. 