C Recursion
In this tutorial, we will learn about recursive functions and its syntax in C programming with the help of examples.
Recursion
The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as recursive function.
Recursion has got a problem-solving tool, where it dives the larger problems into simple tasks and wirking out individually to follow an individual sequence.
Syntax :
Datatype_of_function Function_identifier(){
.............................
.....code for compiling......
.............................
Function_identifier(); /* Function calls itself */;
}
Datatype_of_function main() {
Function_identifier(); /* Calling recursive function */
}How recursion works?
The recursion used to repeat the code within it by calling itself until a some condition is met to prevent repeating.
In most cases if-else statement are used to prevent to infinite recursion.
Working
- Recursion performs repetition on the function calls, and it stops the execution when the base case becomes true.
- In Simple words, The recursion continues until some condition is met.
- A base case condition should be defined in the recursive function to avoid stack overflow errror messages.
- If no base case is defined it leads to infinite recursion.
- To prevent infinite recursion, if...else statement (or similar approach) can be used where one branch makes the recursive call and the other doesn't.
Example: Sum of Natural Numbers Using Recursion
#include <stdio.h>
int fact(int);int main() {
int num, factorial;
printf("Enter a positive integer: ");
scanf("%d", &num);
factorial = fact(num);
printf("Factorial = %d", factorial);
return 0;
}
int fact(int num) {
if (num == 0){
return 0;
}
else if (num == 1){
return 1;
}
else
return num*fact(num - 1); // fact() function calls itself
}Output
Enter a positive integer: 8
40320
Working of Recursive function in the above example
| Cycle | Else return | If return | Result from if-else |
|---|---|---|---|
| 1st | Execute | Not Execute | return 8*fact(7) = 40320 |
| 2nd | Execute | Not Execute | return 7*fact(6) = 5040 |
| 3rd | Execute | Not Execute | return 6*fact(5) = 720 |
| 4th | Execute | Not Execute | return 5*fact(4) = 120 |
| 5th | Execute | Not Execute | return 4*fact(3) = 24 |
| 6th | Execute | Not Execute | return 3*fact(2) = 6 |
| 7th | Execute | Not Execute | return 2*fact(1) = 2 |
| 8th | Execute | Not Execute | return 1*fact(0) = 1 |
| 9th | Not Execute | Execute | N/A |
In the above program, fact() function is called from main() function. Then the 1st recursive cycle of fact() function takes place, then recursion of fact() function starts until some condition met to prevent repeating and that condition is num == 0 .
After the completion of complete 8 recursion cycles of fact() function, num == 0 condition met and if statement executes to prevent recursive cycles.
Advantages of Recursion
- It makes our code shorter and cleaner.
- Recursion is required in problems concerning data structures and advanced algorithms, such as Graph and Tree Traversal.
Disadvantages of Recursion
- It takes a lot of stack space compared to an iterative program.
- It uses more processor time.
- It can be more difficult to debug compared to an equivalent iterative program.
Next Tutorial
We hope that this tutorial helped you develop better understanding of the concept of Recursion in C.
Keep Learning : )
In the next tutorial, you'll learn about C Storage Class.