Problem-solving skills are necessary for every Programming Language, we need to see through the problem and understand it first, like its algorithm, how it works, and all such things. This technique is very much useful for solving problems, but in the case of really complex problems, what if we are only able to think of a single sub-case of the problem and we have to iterate it over and over again. This would not only make our solution big and complex but also increases time complexity and reduces the clarity also. In such cases - Recursion comes into play.
Recursion is defined as a technique in which larger or complex problems are broken down into smaller and simpler problems or instances of the same form. It is actually defining something in terms of itself. Recursion is done with the help of functions, where the function calls itself again and again, within its own code. Such a function is known as a Recursive Function.
Here, In the function, there is a term named BASE CASE, it is the final case until which our problem will be executed. Like in terms of factorial, we have to find the solution until the last number to be multiplied is the number itself or if a reverse loop is applied then it is 0. So we can say 0 is the base case and when it is reached we should return an integer, and here it would be 1. This does not mean that a problem will have only 1 base case, it can have either 2 also, like in the problem of the Fibonacci Series.
What will happen if no Base Case is given?
The answer here is very simple, if we do not define the bases case, the program would continue to run forever. Not forever it would display an error message of Stack Overflow. This occurs because when a recursive function is called it occurs as a fresh function call, and its entry is recorded on the stack and a copy of local variables is created again and again for the functions which occupy memory, this memory occupied in the stack is released whenever the base case is reached, and in the absence of it the stack keeps on growing, and stack overflow occurs.
Tailed and Non-tailed Recursion!
If the last action of the function called is to recall it, then it is said to be a tailed recursion. Otherwise, if the re-call is made in between or somewhere except the ending, then it is termed as Non-tailed recursion.
Program 1. Printing the factorial of a number using recursion.
#include <stdio.h>
int fact(int num)
{
if (num == 0)
return 1;
else
return (num * fact(num-1));
}
int main()
{
int number, fact1;
scanf("%d",&number);
fact1 = fact(number);
printf("The Factorial of %d is %d\n",number,fact1);
return 0;
}
OUTPUT
5
The Factorial of 5 is 120
HOW IT WORKS
When main() starts, the user is asked to input a number (Suppose 5), the fact() function is called. In the fact function, it checks if the number sent as an argument is equal to 0 or not. Here 5 is not equal to 0, so else case starts, in else it returns 5*fact(5-1) , i.e, 5*fact(4). Now fact() again executes for the value of 4, and this time returns 4*fact(3) and it continues until the number as argument becomes 0, i.e our Base Case. and then we get our final answer. Like this.
Fact(5) = 5 * fact(4)
= 5 * (4 * fact(3))
= 5 * (4 * (3 * fact(2)))
= 5 * (4 * (3 * (2 * fact(1))))
= 5 * (4 * (3 * (2 * (1 * fact(0))))) //for fact(0) function returns 1
= 5 * (4 * (3 * (2 * (1 * 1))))
= 5 * (4 * (3 * (2 * 1 )))
= 5 * (4 * (3 * 2))
= 5 * (4 * (6))
= 5 * 24
= 120
So the final answer returned is 5*24, i.e 120.
Program 2. Find the sum of the first N-Natural Numbers using recursion.
#include <stdio.h>
int sum(int n)
{
if (n != 0)
return n + sum(n-1);
else
return n;
}
int main() {
int number, r;
printf("Enter an integer: ");
scanf("%d", &number);
r = sum(number);
printf("sum of first N-natural numbers is %d", r);
return 0;
}
OUTPUT
Enter an integer:5
the sum of the first N-natural numbers is 16
HOW IT WORKS
Here also the same procedure is followed as above but except for the return values being multiplied, they are added up, to give the desired value.
Returning 16 as the answer.
Program 3. Print Fibonacci Sequence up to a particular number using recursion.
* Fibonacci series is a series of numbers in which each number is the sum of the preceding 2 numbers.
Example: 0 1 1 2 3 5 8 and so on.
#include<stdio.h>
int f(int);
int main()
{ int n, i, c;
printf("Enter number:");
scanf("%d", &n);
i=n-1;
for (c = 1; c <= n; c++)
{
printf("%d\n", f(i));
i--;
}
return 0;
}
int f(int n)
{
if (n == 0 || n == 1)
return n;
else
return (f(n-1) + f(n-2));
}
OUTPUT
Enter number:4
0 1 1 2
Problem 4. Write a program to find the GCD ( Greatest Common Divisor ) using Recursion.
#include<stdio.h>
int gcd(int i, int j)
{
while (i != j)
{
if (i > j)
{
return gcd(i-j,j);
}
else
{
return gcd(i,j-i);
}
}
return I;
}
int main()
{
int n1,n2,i,a;
scanf("%d %d",&n1,&n2);
a=gcd(n1,n2);
printf("GCD of %d and %d is %d",n1,n2,a);
return 0;
}
OUTPUT
30 18
GCD of 30 and 18 is 6
Program 5. Finding Prime factors of a number using Recursion.
#include <stdio.h>
void prime(int);
int main()
{
int no;
scanf("%d",&no);
prime(no);
return 0;
}
void prime(int n)
{
static int i=2;
if(i<=n)
{
if(n%i==0)
{
printf("%d ",i);
n/=i;
}
else
{
i++;
}
prime(n);
}
}
OUTPUT
24
2 2 2 3
Program 6. Find the answer by solving the exponential power of a given base.
#include<stdio.h>
int power(int base, int exp)
{
if(exp==0)
return 1;
else
{
return (base*power(base,exp-1));
}
}
int main()
{
int base,exp,ans;
scanf("%d %d",&base,&exp);
ans=power(base,exp);
printf(" %d raise to power %d is %d",base,exp,ans);
}
OUTPUT
3 4
3 raised to power 4 is 81
Program 7. Find the Binary representation of the Decimal number using Recursion.
#include<stdio.h>
int decimalToBinary(int n)
{
int r;
if(n==0)
return 0;
else
{
r=n%2;
r+=decimalToBinary(n/2)*10;
return r;
}
}
int main()
{
int dec,ans;
scanf("%d",&dec);
ans=decimalToBinary(dec);
printf("The Binary representation of %d is %d",dec,ans);
return 0;
}
OUTPUT
43
The binary representation of 43 is 101011
Advantages of Recursion
- Reduces Time-complexity.
- Adds clarity to our code.
- Decreases the time required to debug our code.
- Better at Tree Traversal
Dis-advantages of recursion
- Recursion uses more memory in the system than iteration techniques.
- It is also slower
Like the way you explained the programming in a very well manner,..
ReplyDeleteKeep it up..
You may also check out my blog by clicking below..
Dr. Kalam Book Review
I always love to read these kind of blog..loved it
ReplyDeleteKeep it up