C Program Using Recursion
Recursion:
A general definition of recursion is the repetition of a process in a similar manner up until the desired condition is met.
Recursion is the term used in C programming to describe a function that calls itself from within.
Both the function that calls itself and the function call are referred to as recursive operations.
Iteration and recursion are similar, but recursion is harder to comprehend. If the issue can be resolved by recursion, it can also be resolved through iteration. Recursion can be used to find solutions to issues with sorting, traversal, and searching.
Recursion must have a base (exit) condition in order to be used; otherwise, the application will enter an infinite loop.
The programme body of the recursion has two cases.
Base case: A certain condition in the function serves as the base case when writing recursive methods or functions since they repeatedly call themselves. It puts an end to the recursion when it is reached.
It is employed to guarantee that the programme will end. Otherwise, it enters an endless loop.
Recursive case: The recursive case is the section of the recursive function that runs repeatedly when the recursive function is being called.
Syntax:
void recursive() //recursive function
{
Base_case; // terminating Condition
recursive_fun(); //recursive call
}
int main()
{
recursive(); //calling a recursive function
}
Types of Recursive Functions in C:
The C programming language supports two types of recursions.
1. Direct Recursion
2. Indirect Recursion
1. Direct Recursion in C:
In C, direct recursion happens when a function directly calls itself from within. These processes are also known as direct recursive processes.
Here is the direct recursion's structure.
function_name()
{
//code
function_name();
//code
}
Example for Direct Recursion:
#include<stdio.h>
int fibonacci_series(int i)
{
if (i == 0)
{
return 0;
}
if (i == 1)
{
return 1;
}
return fibonacci_series(i - 1) + fibonacci_series(i - 2);
}
int main()
{
int i, num;
printf("Enter the value for fibonacci series:");
scanf("%d", & num);
for (i = 0; i < num; i++)
{
printf(" %d ", fibonacci_series(i));
}
return 0;
}
OUTPUT:
![C Program Using Recursion](https://static.tutorialandexample.com/c/c-program-using-recursion1.png)
Explanation:
- We have declared a function called fibonacci_series() in the C programme shown above. It returns the ith element of the Fibonacci sequence after receiving an integer input of the form i.
- The main() method, where we have taken two variables, i and n, will be executed first.
- The user's input will be kept in n, and the for loop will run until n iterations, passing the parameter to the fibonacci_series() function, where the logic for the Fibonacci series is written, with each iteration.
- We have nested if-else statements inside the fibonacci_series() code now. It will return 0 if the input is zero and 1 if the input is one. These are the Fibonacci function's fundamental cases.
- Fibonacci(i) will recursively return fibonacci_series (i - 1) + fibonacci_series (i -2) if the value of i is larger than 1, and this recursion will be calculated till the base condition.
2. Indirect Recursion in C:
When a function calls another function and then the second function calls the first function once more, this is known as indirect recursion in the C programming language.
The indirect recursion's structure is listed below.
function_01()
{
//code
function_02();
}
function_02()
{
//code
function_01();
}
Function_01() executes and calls function_02() as part of the indirect recursion structure. Function_02 executes after calling now, and within it, the first calling function, function_01, is called.
Example for Indirect Recursion:
Here is a C programme to print numbers from 1 to 10 in a way that prints the odd number plus one whenever it appears.
We display an even number minus 1 and increase the current number at each step when it is encountered.
#include<stdio.h>
void odd();
void even();
int num=1;
void odd()
{
if(num <= 10)
{
printf("%d ", num+1);
num++;
even();
}
return;
}
void even()
{
if(num <= 10)
{
printf("%d ", num-1);
num++;
odd();
}
return;
}
int main()
{
odd();
}
OUTPUT:
![C Program Using Recursion](https://static.tutorialandexample.com/c/c-program-using-recursion2.png)
Explanation:
- We have functions called odd() and even() in this C application. Since we must accept values between 1 and 10, we give the variable n a value of 1.
- We now have an if statement inside the odd() method that says to add 1 to the value of n and output it if it is less than or equal to 10. Then the even() function is invoked, and the value of n is increased by 1 (making it even).
- We now have another if statement inside the even() method that says to deduct 1 from n and print if n is less than or equal to 10.
- The odd() method is then run after increasing n by 1 (making it odd). The if condition within both functions is not satisfied at the end of this indirect recursion.
- The main() function, which we refer to as the odd() function because the initial number handle is 1, is finally present within.
Implementing Factorial of a Number using Recursion:
#include<stdio.h>
int factorial(int n)
{
if(n == 0)
return 1;
else
return (factorial(n-1)*n);
}
int main() { int n,fact; printf("Enter a number: "); scanf("%d",&n); fact = factorial(n); printf("Factorial of %d = %d",n,fact); return 0; }
OUTPUT:
![C Program Using Recursion](https://static.tutorialandexample.com/c/c-program-using-recursion3.png)
Conclusion:
In the C language, there are two types of recursion. Indirect recursion follows directly after the first kind.
When a function calls itself directly from within, it engages in direct recursion in C.
When one function calls another, and that function then calls the original function once more, this is known as indirect recursion.
Recursive calls are made when a function calls itself; as a result, the function itself becomes recursive.
The stack is kept in memory to hold all of the variables with values provided to them as well as the recursive calls.