Recursion in C
It is the process in which a function repeatedly calls itself. It should be noted that during recursion we must specify some condition with which the function will stop execution.
If we don’t specify any condition, the program will go on until the run time stack overflows. Recursion function can be used to solve problems where solution is expressed in terms of successively applying the same solution to the subsets of the problem.
Recursive function allows you to divide your complex problem into identical single simple cases which can be handled easily. This is also a well-known computer programming technique called divide and conquer.
In theory, all recursive functions can be alternatively created by using iterative statements.
In case number of recursive calls is very large, the run time stack can overflow, so we should implement recursive function using iteration.
Advantages of Recursion
- Program code becomes compact.
- It becomes easier to understand and write the program.
- Recursive functions are simpler than iteration.
- It can be used to implement complex data structures like tree, linked list etc. For Example we can use recursion to traverse a tree or nodes of a linked list.
Disadvantages of Recursion
- It may result in infinite loop if proper condition is not implemented to stop the recursion.
- Recursion is less efficient as compared to a normal function in terms of time of execution.
- The speed of recursive function is slow.
| Program to find factorial of a number using recursion. |
| #include<stdio.h> int factorial(int n) { if(n==1||n==0) return(1); else return(n*factorial(n-1)); } int main() { int f,m; printf(“\nEnter the number whose factorial you want=”); scanf(“%d”,&m); f=factorial(m); printf(“\nFactorial=%d”,f); return(0); } |
| Output |
| Enter the number whose factorial you want=5 Factorial=120 |
| Description |
In the above program, factorial of a number has been generated by using a recursive function factorial() . This function accepts one int type argument and returns int value. Inside the function body, we check that whether value of argument n is equal to 1 or 0. n is an integer variable which contains value passed from main function i.e. value of integer variable m. If user enters 1 or 0, then the factorial will be 1. The calculate factorial the statement n*factorial (n-1); will execute. Suppose n is 5, execution will be as follows: f = 5* factorial (5-1); will be evaluated. This statement again calls factorial() function with value n-1 which will return value 4*factorial(4-1); This recursive calling continues until value of n is equal to 1 or 0 and when n is equal to 1 it returns 1 and execution of this function stops. We can review the series of recursive call as follow: f = 5* factorial (5-1); f = 5*4* factorial (4-1); f = 5*4*3* factorial (3-1); f = 5*4*3*2* factorial (2-1); f = 5*4*3*2*1; f = 120; |
| Program to print Fibonacci series using recursion |
| #include<stdio.h> int fib(int n) { if(n==1) return(1); else if(n==0) return(0); else return(fib(n-1)+fib(n-2)); } int main() { int m,i,f; printf(“\nHow many terms are required in fibonacci series=”); scanf(“%d”,&m); for(i=0;i<m;i++) { f=fib(i); printf(“\t%d”,f); } return(0); } |
| Output |
| How many terms are required in fibonacci series=6 0 1 1 2 3 5 |
| Description |
| In the above program, value of variable m is input inside main() function. Then for statement is applied as for(i=0;i<m;i++) { f=fib(i); printf(“\t%d”,f); } for i=0, function fib is called as fib(0). So 0 goes to formal argument n, where it is compared and 0 is returned back to main().Then 1 goes to formal argument n, where it is compared and 1 is returned back to main().Then 2 goes to formal argument n, where fib(n-1)+fib(n-2) gets executed as fib(1)+fib(0) and 1 is returned back to main().Similary for each consecutive value fib(n-1)+fib(n-2) gets executed and next value of fibonacci series is returned back to main(). |
Nesting of functions in C
It is the process in which a function calls another function. Nesting is basically performed to simplify the task to function calling but excessive nesting of functions may result in complex programs which may be difficult to understand and debug. So nesting of functions should be performed very carefully.
| Program to demonstrate nesting of function. |
| #include<stdio.h> void msg() { printf(”\nHello”); } void show() { printf(”Welcome”); msg(); /*Function message() nested within function show().*/ } int main() { show(); return(0); } |
| Output |
| Welcome Hello |
Test Your Knowledge
Write C program for following:
- Program using recursion to fine Xy.
Best Books of C