RECURSION IN JAVA

Recursion in Java is the process of making a call' to a function itself. This technique offers a means of breaking down complicated problems into simple, easier to solve problems. Using recursion certain problems can be solved easily.

Table of Contents

[hide]
  • What is recursion in Java
  • Recursion Vs Iteration
  • Fibonnaci using recursion

What is recursion in Java

Recursion in Java is used as a form of repetition that does not involve iteration. The function definition that calls itself is also known as recursion function. That is, a function is said to be recursive if the function definition includes a call to itself eg :

Example : Recursive function

 void recur(){
     .
     .
     recur(); // calling itself
 }

There can be two types of recursions in Java :

  • 1. Direct Recursion
  • 2. Indirect Recursion

The above example, where a function calls itself directly from within its body is an example of direct recursion.

However if the function calls another function which calls its caller function from within its body, can be termed as indirect recursion. Lets see an example of the same :

Example : Indirect Recursion

 void recur(){
    codebator();
 }

 codebator(){
     recur();
 }

Before we start working on recursive function, we must know that every recursive function must have at least two cases :

  • 1. Recursive Case (inductive case)
  • 2. Base case (stopping case)

Base case is a small problem that we know how to solve and is the case that causes the recursion to end. This is the case whose solution is pre-known and is used without computation.

Recursive case is the more general case of the problem, where we try to solve the problem with recursive function.

Example : Factorial in Java using recursion

copyimage
//Java Program to demonstrate the use of recursion in Java
import java.util.*;
class Factorial { 

     public int fact(int n) {
     if(n < 2) // base case
         return 1;
     else  
         return n*fact(n-1); // recursive call	
     } 
} 
public class Codebator { 
  public static void main (String[] args) { 
     Scanner sc=new Scanner(System.in);
     System.out.print("Enter any number ");
     Factorial obj = new Factorial();
     int n=sc.nextInt();
     int fact=obj.fact(n);
     System.out.println("Factorial of the given number is " + fact);
    }
} 

OUTPUT :

Enter any number 6Factorial of the given number is 720 

Working :

6 * fact(5)6 * 5 * fact(4)6 * 5 * 4 * fact(3)6 * 5 * 4 * 3 * fact(2)6 * 5 * 4 * 3 * 2 * fact(1)6 * 5 * 4 * 3 * 2 * 1 = 720

If there is no base case, the your function will go into an infinite recursion. Infinite Recursion is when a recursion function calls itself endlessly. This is also known as halting condition.

Now lets solve the same problem iteratively :

Example : Calculate Factorial iteratively

copyimage
//Java Program to demonstrate the use of recursion in Java
import java.util.*;
class Factorial { 

     public int fact(int n) {
     int fact = 1;
     for(int i = n ; i >0 ; i--)
         fact = fact * i;
     return fact;
     }
} 
public class Codebator { 
  public static void main (String[] args) { 
     Scanner sc=new Scanner(System.in);
     System.out.print("Enter any number ");
     Factorial obj = new Factorial();
     int n=sc.nextInt();
     int fact=obj.fact(n);
     System.out.println("Factorial of the given number is " + fact);
    }
} 

OUTPUT :

Enter any number 6Factorial of the given number is 720 

Recursion Vs Iteration

When a loop repeats, it uses same memory locations for variables and repeats the same unit of code. Whereas in recursion, instead of repeating the same unit of code and using the same memory locations for variables, fresh memory space is allocated for each recursive call.

Any problem that can be solved via iteration can be solved using recursion and any problem that can be solved via recusion can be solved using iteration.

Iteration is preferred by programmers for most recurring events. In a programming language, recursion involves an additional cost in terms of the space used in the RAM by each recursive call to a function.

Because of extra memory stack manipulation, recursive versions of functions often run slower and use more memory than their iterative counterparts. But this is not always the case and recursion can sometime make code easier to understand.

Fibonnaci using recursion

copyimage
//Java Program to demonstrate the use of recursion in Java
import java.util.*;
class Fibonacci { 

     public static int getFibonacci(int total) {
        //Base Case
        if (total <= 1){
            return total;
        }
            return getFibonacci(total-1) + getFibonacci(total-2);
     } 
}
public class Codebator { 
   public static void main (String[] args) { 
        Scanner sc=new Scanner(System.in);
        System.out.print("Enter any number ");
        int n=sc.nextInt();
        for (int i= 0; i < n; i++)
        System.out.print(Fibonacci.getFibonacci(i)+" ");
   }
}

OUTPUT :

Enter any number 100 1 1 2 3 5 8 13 21 34