Java – Recursion

Recursion is a programming technique where a method calls itself to perform a sub-operation as necessary. The method which is calling itself is termed as a recursive function. Recursion is primary used to break big problems into smaller problems and then solving them recursively. Recursion technique makes code more readable and expressive.

Example

Consider the following case −

// recursive method
public int sum(int n){
   // recursive method call
   return n == 1 ? 1 : n + sum(n-1);
}

In this case, we”re getting sum of n natural numbers using recursion which can be tabulated as n + sum of n – 1 numbers. Using recursion, we are adding the result of sum of n-1 natural numbers with n to get the required result.

As a recursive function calls itself, there must be a base condition based on which the recursive method can stop calling itself indefinitely. If base condition is not present or never comes true, then it will cause a stack overflow in program. In above example, we”re having a base condition of n being 1.

public int sum(int n){
   // base condition
   if(n == 1){
      return 1;
   }
   // recursive call
   return n + sum(n-1);
}

If we call this function with a negative int value, then it will cause a stack overflow error.

How Recursion Works in Java?

In Java, variables, method call, references are stored in stack whereas objects are allotted memory in heap. Whenever a method is called, its details are pushed to the stack like value of the argument passed, any local variable, computation etc. During recursive call, whenever a method calls itself, its entry is pushed to the stack till the base condition terminates the flow. When base condition comes true, and method starts returning the value, the result of sub call is popped from the stack and so on till the all entries of method is popped from the stack. Let”s understand this with an example.

Example

package com.tutorialspoint;

public class Tester {
   public static void main(String[] args) {
      Tester tester = new Tester();
      int result = tester.sum(5);
      System.out.println("Sum: " + result);
   }

   public int sum(int n){
      System.out.println("Input: " + n);
      int result;
      // base condition
      if(n == 1){
         result = 1;
         System.out.println("Base condition fulfilled.");
      }else {
         // recursive call
         result = n + sum(n-1);
      }
      System.out.println("Result: " + result);
      return result;
   }
}

Output

Let us compile and run the above program, this will produce the following result −

Input: 5
Input: 4
Input: 3
Input: 2
Input: 1
Base condition fulfilled.
Result: 1
Result: 3
Result: 6
Result: 10
Result: 15
Sum: 15

In this program, we can see easily that during recursive calls, initially input value is getting printed till the base condition is fulfilled as method calls are being pushed to stack. Once base condition is fulfilled, the recursive calls finished and method result is getting popped from the stack as evident from the output.

Java Recursion Examples

1. Calculating Factorial Using Recursion

factorial is a mathematical expression which represents the following formulation.

n! = n * (n-1)!

This kind of the problems are perfect candidates to be solved using recursion. Consider the following code snippet.

fact(n) = n * fact(n-1)

Here a fact() is method which is to return the factorial of a given natural number. Now before implementing the fact(), we should think on base conditions are well which should be as following.

1! = 1

Now let”s see the complete example for factorial using recursion.

package com.tutorialspoint;

public class Tester {
   public static void main(String[] args) {
      Tester tester = new Tester();
      // call the recursive method to get the factorial
      int result = tester.fact(5);
      System.out.println("Factorial: " + result);
   }
   // recursive method
   public int fact(int n) {
      // if base condition is not true, make a recursive call
      return n == 1 ? 1: n * fact(n-1);
   }
}

Output

Let us compile and run the above program, this will produce the following result −

Factorial: 120

2. Calculating Sum of Fibonacci Series Using Recursion

fibbonacci series is a very important and interesting series in mathematics. It represents the follwing equation −

F(n) = F(n-1) + F(n-2)

Here, we cand say, fibbonacci number represents the sum of its predecessor and the next predecessor. A fibbonacci series is of form 0, 1, 1, 2, 3, 5 and s on.

Using recursion, we can easily compute the fibbonacci number. Consider the following code snippet.

fibo(n) = fibo(n-1) + fibo(n-2)

Here a fibo() is method which is to return the fibonacci of a given whole number. Now before implementing the fibo(), we should think on base conditions are well which should be as following.

fibo(0) = 0;
fibo(1) = 1;

Now let”s see the complete example for fibonacci number computation using recursion.

package com.tutorialspoint;

public class Tester {
   public static void main(String[] args) {
      Tester tester = new Tester();
      int result = tester.fibo(5);
      System.out.println("Fibbonacci: " + result);
   }

   public int fibo(int n) {
      return n <= 1 ? n : fibo(n-1) + fibo(n-2);
   }
}

Output

Let us compile and run the above program, this will produce the following result −

Fibbonacci: 5

Advantages of Using Recursion in Java

Following are the advantages of using recursion in Java:

• Cleaner code Using recursion makes code easy to understand and keeps code clean. Instead of using multiple if and loops conditions, recursion helps in writing code in functional way.
• Recursive algorithm For certain problem, like tree traversal, tower of hanoi problem etc, recursion is the best apporach to code the solution.
• Reduces time complexity Recursive program helps in reducing time taken in searches on large datasets.

Disadvantages of Using Recursion in Java

Following are the disadvantages of using recursion in Java:

• Expertise Recursion although is a cleaner approach but required high amount of expertise and understanding of the problem statement and proposed solution. An incorrectly implemented recursion may cause performance issues and may be hard to debug.
• Memory space intensive Being multiple function calls involved and return flows, recursive programs are generally memory intensive.