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.

What's next?

Array Representation