Recursion in C with program
Written by
Recursion in C
What do you understand by recursion ?
As the word itself suggests, recursion is something that you are doing repeatedly. But you might thing aren’t iteration and recursion the same then ? Well, they are not and you will understand the same after going through the concept of recursion.
Definition:
Recursion or Circular Definition is a process in which a function calls itself directly or indirectly and the corresponding function is called recursive function. It is a technique wherein a function calls itself with a smaller part of the function/task in order to solve that problem. It is a process of defining something in terms of itself.
Where is it used ?
There are multiple applications of recursion. They are useful when the solution to a larger problem can be expressed and solved in terms of its smaller components. It enables us to express the operation in term of themselves.
Since it breaks a larger problem into smaller parts to solve a given task; it is said to follow a top-down approach or Divide and Conquer.
To understand recursion , consider you building a pillar, you would first place the foundation bricks , over it you will continue repeating the same ‘action/task’ until the required dimensions are achieved.
Examples:
- To solve mathematical problems like Fibonacci series, factorial, greatest common divisor etc.
- Traversal of trees: pre-order / post order etc. Best example could be traversing a directory structure in your computer, you repeatedly go on opening sub directory of the main directory until the desired file/directory is reached.
How to use recursion in C ?
A recursive function has two major components:
- Base Case:It is the condition which is checked every time which decides if further function call needs to be done or not. It is simple to solve and will not include any function call. Base case has to be there when defining recursive function, else the system will go into an indefinite loop. We shall discuss about it in the next section about recursion and stack.
- Recursive Case: In order to solve a problem using recursion the following steps needs to be followed:
- The main problem will be broken down into simpler sub parts.
- The function will call itself using the simpler sub parts developed in step 1.
- The result is obtained by combining solutions obtained from all the sub-parts.
Syntax:
returntype recursive_function_name ([argument_list[])
{
statements...
base case;
.........
recursive_function_name([actual argument/parameter])
}
Workflow of recursion:
Let us understand recursion with the help of an example:
1.) Factorial of a number:
Factorial of a number n is given as n*(n-1)!. That is the number is multiplied with its successive numbers until number 1 is reached.
Thus our recursive function becomes n*(n-1) , wherein we are defining the operation in terms of itself , but with a smaller value of n every single time.
it can be given as : fact (n) = n*fact(n-1)
Base Case: If n = 1, we know 1! = 1.
Consider 5 !
5 ! = 5 * 4 !
= 5*4*3!
= 5*4*3*2!
= 5*4*3*2*1!
Thus this is how our recursive function will be called.
The solution will be as follows: (The reason it is in this order, we will understand it at a later section)
5*4*3*2*1!
= 5*4*3*2*1
=5*4*3*2
=5*4*6
=5*24
=120.
Program:
#include<stdio.h>
int fact(int);
int main()
{
clrscr();
int no;
printf("Enter the number whose factorial is to be calculated:\n");
scanf("%d",&no);
printf("Factorial of %d is %d \n", no, fact(no));
getch();
return0; }
int fact(int n)
{
if(n==1)
return 1;
else
return ( n*fact(n-1));
Output:
Enter the number whose factorial is to be calculated: 5 Factorial of 5 is 120
Now let us understand how does it exactly function:
- First the function will be called with its largest problem, that is here n = 5. Hence, fact(5) will be given to recursive function.
- Base case will be checked every time recursive function, here factorial will be called. Since condition does not satisfy the else part is executed; the recursive part.
- Now the function is called with its smaller part which is n-1; i.e 4. Thus the return value would look like this return 5*fact(4).
- In the similar fashion, function factorial will be recursively called until n=1, that is 1!=1 case. The last call would be as follows: return 1*fact(0)
Kindly note that , the breakdown of the problem has happened in a top down approach.
- When the base case is satisfied, the value returned would be 1. This is the point where the solutions of the smaller sub parts start getting combined to get the final answer.
Do you remember, when we discussed this problem numerically we told that we would discuss why the solution gets combined in the reverse order ?
Let us understand that now.
Recursion is implemented by the compiler using a data structure called stack. It is an area in computer memory where recursive functions are executed.
It is a Last in First Out (LIFO) data structure, meaning the element that goes in last is the first one to exit. Relate it to a stack of plates, the plate placed on the top which is the last one is taken out first for serving.
When, program initialises the recursive function, all data pertaining to it, variable initialisation, function calls get pushed onto the stack one upon other as and when function gets called. We see that in our factorial problem, fact(5) is the first plate in our stack, and fact(0) will be the last plate.
Once , base case gets satisfied, the computation of solution begins. Now the last plate in our stack will be taken out first to compute. Hence, the solution gets calculated in the LIFO approach.
This is how recursion functions.
Note: Since, recursion uses stack always remember to include the base case/ condition. If it is not properly defined or skipped, the function will be infinitely called leading to stack overflow at one point; since stack is not a large space in computer memory.
Advantages:
- Recursive functions tend to be shorter, simpler.
- Code readability is improved as it is easier to use and understand.
- The original formula is used to solve the problem.
- Follows Divide and Conquer Approach.
- In certain cases, recursion is more preferred.
Disadvantages:
- Since recursion is run using stack, if stack space is limited on the system recursion will not be able to execute at a deeper level.
- Base condition needs to be defined carefully, as otherwise infinite recursion would lead to stack overflow.
- It takes longer time to execute ; is slow since each time function is called a number of operations / addresses etc needs to be pushed and then ultimately popped out of stack.
- It has a lot of overhead involved in terms of time and memory consumed.
- It is challenging to find bugs when using global variables.
Program to Learn:
Write a program using recursion to Calculate Greatest Common Divisor Using Euclid’s formula.
Try and make flowchart for function call and solution build to understand better.
Given: GCD is largest integer that divides given 2 numbers. Formula is :
GCD (x,y) = y , if y divides x ; assuming x > y else interchange positions of x and y.
= GCD (y, x mod y) -> recursive case
Example: Always take x > y to use this formula.
GCD (40,20) = 20
GCD (78, 8) = GCD (8, 78 mod 8 ) = GCD (8, 6 )
= GCD (6, 8 mod 6) = GCD (6, 2)
= GCD (2, 6 mod 2 ) = GCD (2, 0)
return 2.
Program:
#include <stdio.h>
int gcd(int, int);
int main()
{
int num1, num2;
printf("Enter two numbers: ");
scanf("%d%d", &num1, &num2);
printf("The greatest common divisor of %d and %d is %d", num1, num2, gcd(num1, num2));
return 0;
}
int gcd(int x, int y)
{
if (x % y == 0)
return y;
else
return gcd(y, x % y); }
Output:
Enter two numbers: 78 8 The greatest common divisor of 78 and 8 is 2.
