Headlines
Loading...
What problems can be solved using recursion?

What problems can be solved using recursion?

In this tutorial we will look some great problems which can be solved using recursion. 


Sum of N
Explanation: 1+2+3+4....n we need to print the output of sum of n.
// 1+2+3+4...+n

#include <stdio.h>
int sum(int n)
{
if(n==0)
{
return 0;
}
return sum(n-1)+n;
}

int main(void) {
printf("%d", sum(4));
return 0;
}

Factorial
#include <stdio.h>
int fact(int n)
{
if(n==0)
{
return 1;
}
return fact(n-1)*n;
}

int main(void) {
printf("%d", fact(5));
return 0;
}

Power
// m^n = m*m*m*m....n times
// power(m,n) = m*m*m*m....(n-1) * m
// power(m,n) = pow(m,n-1) * m

#include <stdio.h>
int power(int m, int n)
{
if(n==0)
{
return 1;
}
return power(m,n-1)*m;
}

int main(void) {
printf("%d",power(2,4));
return 0;
}

Fibonacci Series
// 0 1 1 2 3 5 8 13

#include <stdio.h>
int fib(int n)
{
if(n<=1)
{
return n;
}
return fib(n-2)+fib(n-1);
}

int main(void) {
printf("%d",fib(5));
return 0;
}

nCr Formula (Combination)
#include <stdio.h>
int fact(int n)
{
if(n==0)
{
return 1;
}
return fact(n-1)*n;
}

int c(int n, int r)
{
int t1,t2,t3;
t1 = fact(n);
t2 = fact(r);
t3 = fact(n-r);
return t1/(t2*t3);
}

int main(void) {
printf("%d",c(2,2));
return 0;
}

Tower of Hanoi
#include <stdio.h>
void TOH(int n, int a, int b, int c)
{
if(n>0)
{
TOH(n-1, a, c, b); //a to b using c
printf("%d, %d \n", a,c);
TOH(n-1, b, a, c); //b to c using a
}
}

int main(void) {
TOH(3,1,2,3);
return 0;
}

Any doubts in this questions? Please ask your doubts in comment section. Are you confident in recursion now? I recomment you to practice Leetcode easy recursion question.

0 Comments: