Recursion in Java with Examples (factorial, fibonacci, Tower of hanoi, GCD, power, product, etc) by rcub

Recursion in Java

Recursion in java is a process in which a method calls itself continuously.
A method in java that calls itself is called recursive method.
Or
A method that calls itself is known as a recursive method. And, this process is known as recursion.

Syntax:
<return type > methodname()
{    
   if (precondition == true)
   {
   return result;
    }
     methodname();//calling recursive method
 }  

precondition is also called as
Base condition.
If the base case is not reached or not defined, then the stack overflow problem may arise.

advantages (pros):-

1.Recursion makes the code clearer and shorter.
Or
Recursion reduces the size of the code.
2.Recursion can reduce time complexity.
3.Recursion is better at tree traversal and Tower of Hanoi
4.Reduce unnecessary calling of function.

disadvantages(cons):-
1.Recursion performance is slower than the iterative approach.
2.Recursion uses more memory.

categories of recursion.
1.direct
2.indirect

1.Direct recursion: When function calls itself, it is called direct recursion. 

Syntax :
<return type> method()
{
  method() ;
} 

2.Indirect recursion: When function calls another function and that function calls the calling function, then this is called indirect recursion. 

Syntax :
<return type >method1()
{
Method2() ;
}
<return type >Method2()
{
method1() ;
}

List of Programs solution using recursion.

1.Write a Java program to find factorial of number using recursion in Java.

import java.util.Scanner;
public class Recursion
{
static long fact(int n)
{
if((n==1)||(n==0))
return 1;
else
return n*fact(n-1);
}
public static void main(String args[])
{
Scanner s = new  Scanner(System.in);
System.out.println ("Enter the n final value:");
int n=s.nextInt();
System.out.println ("Factorial is :"+fact(n));
}
} 

OUTPUT:

Enter the n final value:5
Factorial  is: 120

2.Write a Java Program to print Upto N fibonacci series using recursion in Java.

import java.util.Scanner;
public class Recursion
{
static int fib(int n)
{
  if(n>1)
return fib(n-2)+fib(n-1);
else
if (n==1)
return 1;
else
return 0;
}
public static void main(String args[ ])
{
Scanner s = new  Scanner(System.in);
System.out.println ("Enter the n final value:");
int n=s.nextInt();
System.out.println("Fibonacci series  is:");
for(int i=0;i<n;i++)
{
System.out.println(fib(i));
}
}
}
Output :

Enter the n final value:5
Fibonacci series  is:
0
1
1
2
3

3.Write a Java Program to implement tower of hanoi using recursion in Java.

import java.util.Scanner;
public class Recursion

{
public void solve(int n, String source, String aux, String dest)
{
// If only 1 disk, make the move and return.
if(n==1)
{
System.out.println(source+" --> "+dest);
return;
}
// Move top n-1 disks from A to B using C as auxiliary.
solve(n-1, source, dest, aux);
//Move remaining disks from A to C
System.out.println(source+" --> "+dest);
// Move n-1 disks from B to C using A as auxiliary
solve(n-1, aux, source, dest);

}
public static void main(String args[])
{
Recursion obj = new Recursion();
System.out.println("Enter number of disks :");
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
scanner.close();
System.out.println("Move disks as below illustration.");
obj.solve(n, "A", "B", "C");
}
}

Output :

Enter number of disks :2
Move disks as below illustration.
A --> B
A --> C
B --> C

Or
Enter number of disks :3
Move disks as below illustration.
A –> C
A –> B
C –> B
A –> C
B –> A
B –> C
A –> C

4.Write a Java Program to calculate power of number using recursion in Java.

import java.util.Scanner;
public class Recursion

{
int power(int x, int n)
{
if(n==0)
return 1;
else
return x*power(x, n-1);
}
public static void main(String args[])
{  
Recursion obj = new Recursion();
Scanner s = new   Scanner(System.in);
System.out.println("Enter the Base number:");
int x= s.nextInt();
    System.out.println("Enter the exponent number: ");
int n = s.nextInt();
s.close();
System.out.println("Answer is ="+obj.power(x,n));
}
}

Output:

Enter the Base number :3
Enter the exponent number:4
Answer is =81

5.Write a Java program to find the sum of  first N natural Numbers using recursion.

import java.util.*;
public class Recursion
{
static int  sum(int n)
{
if(n==1)
return 1;
else
return n+sum(n-1);
}
public static void main(String args[])
{
Scanner s = new  Scanner(System.in);
System.out.println ("Enter the n final value:");
int n=s.nextInt();
System.out.println ("sum of natural number is :"+sum(n));
}
}

OUTPUT:

Enter the n final value:4
Sum of natural numbers is:10

6. write a Java program to find products (multiplication) of two numbers using recursion.

import java.util.*;
public class Recursion
{
static int  product(int m, int n)
{
if(n==1)
return m;
else
if((m==0) ||(n==0))
return 0;
else
return m+product(m,n-1);
}
public static void main(String args[])
{
Scanner s = new  Scanner(System.in);
System.out.println ("Enter the 1st number:");
int m=s.nextInt();
System.out.println ("Enter the 2nd number:");
int n=s.nextInt();
System.out.println ("product of 2 number is :"+product(m,n));
}
}

OUTPUT:
Enter the 1st number :2
Enter the 2nd number :5
Product of 2 numbers is:10

7.write a Java program to find GCD (HCF) of two numbers using recursion.

import java.util.*;
public class Recursion
{
static int  gcd(int m, int n)
{
if(n==0)
return m;
else
return gcd(n, m%n);
}
public static void main(String args[])
{
Scanner s = new  Scanner(System.in);
System.out.println ("Enter the 1st number:");
int m=s.nextInt();
System.out.println ("Enter the 2nd number:");
int n=s.nextInt();
System.out.println (" GCD of 2 number is :"+gcd(m,n));
}
}

OUTPUT:

Enter the 1st number :8
Enter the 2nd number :12
GCD of 2 numbers is:4