Introduction to C Recursion
Recursion in C language is a process in which a function calls itself. This is done to solve a problem by dividing it into smaller parts. Functions that call themselves are called recursive functions.
Suppose you are creating a function to solve a problem and its initial result is not the end result. To get the end result you need to repeat this process back.
In such a situation, instead of doing an iteration to execute the same process, you call the same function with the initial result. This process keeps running until the end result is achieved. The end result is determined by the condition.
This process is terminated when the end result is received. If this function is not terminated then it will run till infinite time.
Advantages of Recursion in C language
- When you solve a problem by recursion, you do not need to call the function repeatedly. You call the function only once and till the end result, it keeps calling itself.
- It is very difficult to solve problems through Iteration but in the recursion, the same problem is resolved very easily.
Structure of Recursive Function
The general structure of a recursive function is being given below.
return type myFunction(Parameters-list)
myFunction(Arguments-list); //Calling itself , Recursive process.
Disadvantages of Recursion in C language
- Slower – Recursive programs are slow with ordinary programs. Recursive programs take more time than normal programs to call Function repeatedly to call and end result.
- Requires additional memory – Requires extra memory to execute recursive programs in comparison to ordinary programs.
Types of Recursion
Direct Recursion in C language
Indirect Recursion in C language
Indirect recursion in C language is recursion in which a function calls another function which calls it back. The general structure of such recursion is being given below.
Example of Recursion (Factorial)
To illustrate recursion in C language by example, an example of factorial is being given here. From a factorial number 1 to any number of factorial you want to get, that number is the product (multiplication) of all numbers.
For example, you want to calculate factorial of 5. For this, you have to multiply all numbers from 1 to 5. After multiplying all the numbers, the result which will be achieved will become factorial of 5.
1 * 2 * 3 * 4 * 5 = 120
The c program can have two ways to calculate a number factorial.
- Using iteration – In this manner, you can run the loop from 1 to the given number and multiply all the numbers and then print the result.
- Using recursion – In this manner, you can create a function that multiplies the given number by a number less and calls itself with the same number.
Both of these methods are being explained through an example.
Calculating Factorial of a Number Using recursion in C language
/* factorialIteration.c */
printf("Enter number to find out its factorial.....");
/* Iterating for loop to calculate factorial */
for(i=1; i<=num; i++)
result = result*i;
printf("\nFactorial of %d is %d",num,result);
Calculating Factorial of a Number Using Recursion
/* factorialRecursion.c */
int MyFactFunction(int n);
printf("Enter a number to find its factorial...");
printf("Factorial of %d is : %d",num,MyFactFunction(num));
if(num >= 1) /* Function calling itself to calculate recursion */
In the example given above, MyFactFunction is a recursive function. It calls itself back with a number less than the given number and multiplies with the original value (with which the function was called).
This happens until the original value is greater than 1. As soon as this value becomes 1, this function gets terminate. This program generates the given output below.
Enter a number to find its factorial…
Factorial is : 720