Recursion is an advanced feature provided by Java programming language. The term “recursion” means a method calling itself.

Recursion in Java is a basic programming technique in which a method calls itself repeatedly. A method that calls (or invokes) itself is called recursive method.

In other words, a process in which a method invokes itself directly or indirectly is called recursion, and the related method is called a recursive method.

A recursive method is a chain of method calls to the same method. It is like the loop with or without a terminating condition. It calls itself, either directly or indirectly, via another method.

A famous example often used to describe the recursion in Java is the calculation of factorial (the factorial for a value of 5 is 5 * 4 * 3 * 2 * 1).

Recursion in Java should use best when we need to call the same method repeatedly with different parameters.

It offers some advantages to programmers, such as to develop the neat and short code and also helps to programmers to avoid loops.

Sometimes, the concept of recursion may be a little tricky to understand. But, it is a truth that we can easily solve many programming problems with the help of recursion.

Some programming problems that other techniques can solve are better solved by recursion.

Java Recursion Syntax

The syntax to declare a recursive method in Java that calls itself directly is as follows:

returntype methodname() {
 // code to be executed
    methodname(); // calling the same method
}

How does Java Recursion works?

Look at the below figure to understand the working of recursion in Java.

As you can see in the above example, we have called the recurse() method from inside the main() method. This is a normal method call.

When we are again calling the same recurse() method inside the recurse() method, then it is a recursive call.

The recurse() is a recursive method that is invoking itself inside the method. It is also possible that recursive method invokes itself indirectly.

How to stop Recursion in Java?

We can stop the recursive call by providing some conditions inside the method. While defining recursive method, it is necessary to specify a termination condition. If we do not specify such a condition, then the method may call infinite times.

For this reason, we need to set a condition to terminate the recursion. This condition is called base case or stopping point.

Base case is a condition that prevents infinite recursion. In the base case, no recursive function calls occur.

We can use a simple if…else statement (or similar approach) to terminate the recursive call inside the method.

Recursion Example: Infinite times

Let’s create a Java program in which we will print a message infinite times using the concept of recursion.

Program code 1:

package javaProgram;
public class RecursionExample {
static void display()
{  
  System.out.println("Hello world");  
  display(); // recursive call
}  
public static void main(String[] args) 
{
 display(); // normal method call
  }
}

Output:
       Hello world
       Hello world
       . . .
       . . .
       java.lang.StackOverflowError

Recursion Example: Finite times

Let’s create a Java program in which we will display a message five times using recursion method.

Program code 2:

package javaProgram;
public class RecursionExample {
static int count = 0;	
static void display()
{  
  count++;
  if(count 
Output:
      Hello world
      Hello world
      Hello world
      Hello world
      Hello world

In the above code, we have used a conditional statement in the function body to check the count is less than equal to 5. This is a base condition.
As long as this conditional is true, the recursive method display() calls itself. On each iteration, the count is increasing by 1 and method display() is called until the count is equal to five.
When the count reaches 6, the conditional statement evaluates to false. Since the base condition met, the method will not be called anymore.
Program to count down numbers to 0
Let’s take one more simple example program based on recursion. In this example, we will print numbers from counting down to 0.
Program code 3:
package javaProgram;
public class RecursionExample {
static void countDown(int num)
{
  if(num 
Output:
      4
      3
      2
      1
      0

Factorial Program using Recursion in Java
In this section, we will learn how to compute the factorial of a number using recursion method. A factorial of a number, n, is represented by n!. It is the result of multiplying of a numbers from 1 to n.
For example, the factorial of a number 4 is represented by 4!. It is equal to 4 * 3 * 2 * 1, resulting in 24. General steps to compute the factorial of any number n, as follows:

• (n) * (n – 1) * (n – 2) * (n – 3) * . . . . . * 1.

Let’s write code to compute the factorial of a number using loop in Java.

Program code 4:

// Java program to compute the factorial of a number using loop.
package javaProgram;
public class Factorial 
{	
 static int fact(int num)
 {
   if(num  1; n--)
   {
     total = total * n;
   }
   return total;
  }
public static void main(String[] args) 
{
  System.out.println("The factorial of 6 is " +fact(6));
  }
}

Output:
      The factorial of 6 is 720

In this example, we have computed the factorial starting at given num, and decreases num until it has the value of 2, since the factorial of 1 is 1.

We already included it in the total variable. The factorial of zero is also 1. The factorial of negative numbers cannot compute.

Recursive Factorial

Now, let us rewrite the fact function using recursion.

Program code 5:

// Java program to compute the factorial of a number using recursion.
package javaProgram;
public class Factorial 
{	
 static int fact(int num)
 {
  if(num == 1 || num == 0) // base case.
  {
    return 1;
  }
    return num * fact(num - 1); // recursive call.
 }
public static void main(String[] args) 
{
  System.out.println("The factorial of 6 is " +fact(6));
  }
}

Output:
     The factorial of 6 is 720

Let’s write an algorithm to compute the factorial of number 6. The recursive call to compute the factorial of a number 6 is as:

• fact(6) returns 6 * fact(5)
• fact(5) returns 6 * 5 * fact(4)
• fact(4) returns 6 * 5 * 4 * fact(3)
• fact(3) returns 6 * 5 * 4 * 3 * fact(2)
• fact(2) returns 6 * 5 * 4 * 3 * 2 * fact(1)
• fact(1) returns 6 * 5 * 4 * 3 * 2 * 1.
• fact(1) or fact(0) returns 1. 1! is equal 1 and 0! is also 1.

At the beginning, you may seem that recursive functions are more difficult, but they become easier with practicing some programs.

Fibonacci Series using Recursion in Java

The Fibonacci series is a list of infinite numbers, each of which is the sum of past two numbers (starting with 1). For example, 1, 1, 2, 3, 5, 8, 13, 21, . . . . . . .

Let’s create a Java program to print 20th of the Fibonacci sequence.

Iterative Solution: Fibonacci Series

Let’s write Java code for the Fibonacci series using for loop. This is an iterative solution.

Program code 6:

// Java program to sum the Fibonacci series of a number using for loop.
package javaProgram;
public class Fibonacci 
{	
 static int getFibo(int num)
 {
   if(num 
Output:
      Sum of Fibonacci numbers: 55

In the preceding program, we have used for loop to keep the track of last two elements of the Fibonacci series, and its sum yields the Fibonacci number.
Recursive Solution: Fibonacci Series
Let’s write Java code recursively to yield Fibonacci sequence of a number.
Program code 7:
// Java program to sum the Fibonacci series of a number using recursion.
package javaProgram;
public class Fibonacci 
{	
 static int getFibo(int num)
 {
   if(num 
Output:
      Sum of Fibonacci numbers: 55

Find Sum of digits of a number using recursion
Let’s create a Java program to calculate the sum of its digits of a number using recursion concept. For example, suppose we have a number 12345 as input. Then, the output will be 15. Let’s write the code for it.
Program code 8:
// Recursive java program to calculate sum of its digits of a number.
package javaProgram;
public class Sum_of_digits 
{	
// Create a static method to check sum of its digits using recursion.
   static int getSum(int n)
   {
    if (n == 0)
       return 0;
       return (n % 10 + getSum(n / 10));
    }
public static void main(String[] args) 
{
 int num = 12345;
 int result = getSum(num);
 System.out.println("Sum of digits of a number " +num + " = " + result);
  }
}

Output:
      Sum of digits of a number 12345 = 15

Let’s write an algorithm to compute the sum of its digits of a number. The recursive call to compute the sum of its digits of a number 12345 is as:

• getSum(12345) returns 5 + getSum(12345 / 10)
• getSum(1234) returns 5 + 4 + getSum(1234 / 10 )
• getSum(123) returns 5 + 4 + 3 + getSum(123 / 10)
• getSum(12) returns 5 + 4 + 3 + 2 + getSum(12 / 10)
• getSum(1) return 5 + 4 + 3 + 2+ 1 + getSum(1 / 10)
• 0 algorithm stops.

Program to Spell each Digit Separately

Let’s take one more example program based on the recursive method in Java. Suppose we have an input number and then have to spell each digit separately.

For example, we have a number 789 as input and we have to display 7, 8, and 9 separately. Let’s write the Java code for it.

Program code 8:

package javaProgram;
public class SpellDigit 
{	
 static void spell_num(int number)
 {
  if(number 
Output:
      7
      8
      9

In this example, we have declared a static method named spell_num() that takes as input a parameter number. Within the method body, the method checks if the number is less than 10.
The base case is when the number passed as input is less than 10. As a result, the method will return number itself rather than calling the recursive method. The number will directly display as output on the console. In this case, no recursive call will happen.
If the number is greater than or equal to 10, the method will call recursively, as shown below list and will pass it the quotient of number divided by 10.
Next, the remainder of number divided by 10 will print as output on the console. Because we want to print numbers in correct order from left to right, we will call recursive function first and then print the remainder.
For number 789, the sequence of call of method spell_num is:

• static void spell_num(789) // method called with input 789.
• static void spell_num(78) // method called with input 78.
• static void spell_num(7) // method called with input 7.

Advantages and Disadvantages of Recursion

When a recursive call occurs, JVM allocates new storage locations for variables on the stack. As each recursive call returns, JVM removes the old variables and parameters from the stack and creates a new set of variables.

Hence, recursion uses more memory for processing recursive method. Due to which it is generally slow.

On the other hand, a recursive code is usually smaller, more simple, and concise, more elegant and possible easier to understand.

It is much easy and takes less time to write, debug and maintain the recursion code.

In this tutorial, we have discussed recursion in Java with a lot of example programs. Recursion is a fundamental programming concept we can use in the place of looping and in the many complex programs.

If you seem recursion confusing, don’t worry. At starting, you can feel it, but with practice recursion becomes easier.
Thanks for reading!!!

The post Recursion in Java | Example Program appeared first on Scientech Easy.