This In-depth Tutorial on Recursion in Java Explains what is Recursion with Examples, Types, and Related Concepts. It also covers Recursion Vs Iteration:
From our earlier tutorials in Java, we have seen the iterative approach wherein we declare a loop and then traverse through a data structure in an iterative manner by taking one element at a time.
We have also seen the conditional flow where again we keep one loop variable and repeat a piece of code till the loop variable meets the condition. When it comes to function calls, we explored the iterative approach for function calls as well.
=> Check ALL Java Tutorials Here.
In this tutorial, we will discuss a different approach to programming i.e. the Recursive approach.
Table of Contents:
What Is Recursion In Java?
Recursion is a process by which a function or a method calls itself again and again. This function that is called again and again either directly or indirectly is called the “recursive function”.
We will see various examples to understand recursion. Now let’s see the syntax of recursion.
Recursion Syntax
Any method that implements Recursion has two basic parts:
- Method call which can call itself i.e. recursive
- A precondition that will stop the recursion.
Note that a precondition is necessary for any recursive method as, if we do not break the recursion then it will keep on running infinitely and result in a stack overflow.
The general syntax of recursion is as follows:
methodName (T parameters…)
{
if (precondition == true)
//precondition or base condition
{
return result;
}
return methodName (T parameters…);
//recursive call
}
Note that the precondition is also called base condition. We will discuss more about the base condition in the next section.
Understanding Recursion In Java
In this section, we will try to understand the recursion process and see how it takes place. We will learn about the base condition, stack overflow, and see how a particular problem can be solved with recursion and other such details.
Recursion Base Condition
While writing the recursive program, we should first provide the solution for the base case. Then we express the bigger problem in terms of smaller problems.
As an example, we can take a classic problem of calculating the factorial of a number. Given a number n, we have to find a factorial of n denoted by n!
Now let’s implement the program to calculate the n factorial (n!) using recursion.
public class Main{
static int fact(int n)
{
if (n == 1)
// base condition
return 1;
else
return n*fact(n-1);
} public static void main(String[] args) {
int result = fact(10);
System.out.println("10! = " + result);
}
}
Output
In this program, we can see that the condition (n<=1) is the base condition and when this condition is reached, the function returns 1. The else part of the function is the recursive call. But every time the recursive method is called, n is decremented by 1.
Thus we can conclude that ultimately the value of n will become 1 or less than 1 and at this point, the method will return value 1. This base condition will be reached and the function will stop. Note that the value of n can be anything as long as it satisfies the base condition.
Problem-Solving Using Recursion
The basic idea behind using recursion is to express the bigger problem in terms of smaller problems. Also, we need to add one or more base conditions so that we can come out of recursion.
This was already demonstrated in the above factorial example. In this program, we expressed the n factorial (n!) in terms of smaller values and had a base condition (n <=1) so that when n reaches 1, we can quit the recursive method.
Stack Overflow Error In Recursion
We are aware that when any method or function is called, the state of the function is stored on the stack and is retrieved when the function returns. The stack is used for the recursive method as well.
But in the case of recursion, a problem might occur if we do not define the base condition or when the base condition is somehow not reached or executed. If this situation occurs then the stack overflow may arise.
Let’s consider the below example of factorial notation.
Here we have given a wrong base condition, n==100.
public class Main
{
static int fact(int n)
{
if (n == 100)
// base condition resulting in stack overflow
return 1;
else
return n*fact(n-1);
}
public static void main(String[] args) {
int result = fact(10);
System.out.println("10! = " + result);
}
}
So when n > 100 the method will return 1 but recursion will not stop. The value of n will keep on decrementing indefinitely as there is no other condition to stop it. This will go on till stack overflows.
Another case will be when the value of n < 100. In this case, as well the method will never execute the base condition and result in a stack overflow.
Recursion Examples In Java
In this section, we will implement the following examples using recursion.
#1) Fibonacci Series Using Recursion
The Fibonacci series is given by,
1,1,2,3,5,8,13,21,34,55,…
The above sequence shows that the current element is the sum of the previous two elements. Also, the first element in the Fibonacci series is 1.
So in general if n is the current number, then it is given by the sum of (n-1) and (n-2). As the current element is expressed in terms of previous elements, we can express this problem using recursion.
The program to implement the Fibonacci series is given below:
public class Main
{
//method to calculate fibonacci series
static int fibonacci(int n) {
if (n <= 1) {
return n;
}
return fibonacci(n-1) + fibonacci(n-2);
}
public static void main(String[] args) {
int number = 10;
//print first 10 numbers of fibonacci series
System.out.println ("Fibonacci Series: First 10 numbers:");
for (int i = 1; i <= number; i++)
{
System.out.print(fibonacci(i) + " ");
}
}
}
Output
#2) Check If A Number Is A Palindrome Using Recursion
A palindrome is a sequence that is equal when we read it from left to right or right to left.
Given a number 121, we see that when we read it from left to right and right to left, it is equal. Hence number 121 is a palindrome.
Let’s take another number, 1242. When we read it from left to right it is 1242 and when read from right to left it reads as 2421. Thus this is not a palindrome.
We implement the palindrome program by reversing the digits of numbers and recursively compare the given number to its reversed representation.
The below program implements the program to check the palindrome.
import java.io.*;
import java.util.*;
public class Main {
// check if num contains only one digit
public static int oneDigit(int num) {
if ((num >= 0) && (num < 10))
return 1;
else
return 0;
}
//palindrome utility function
public static int isPalindrome_util (int num, int revNum) throws Exception {
// base condition; return if num=0
if (num == 0) {
return revNum;
} else { //call utility function recursively
revNum = isPalindrome_util(num / 10, revNum);
}
// Check if first digit of num and revNum are equal
if (num % 10 == revNum % 10) {
// if yes, revNum will move with num
return revNum / 10;
}
else {
// exit
throw new Exception();
}
}
//method to check if a given number is palindrome using palindrome utility function
public static int isPalindrome(int num) throws Exception {
if (num < 0)
num = (-num);
int revNum = (num);
return isPalindrome_util(num, revNum);
}
public static void main(String args[]) {
int n = 1242;
try {
isPalindrome(n);
System.out.println("Yes, the given number " + n + " is a palindrome.");
} catch (Exception e) {
System.out.println("No, the given number " + n + " is not a palindrome.");
}
n = 1221;
try {
isPalindrome(n);
System.out.println("Yes, the given number " + n + " is a palindrome.");
} catch (Exception e) {
System.out.println("No, the given number " + n + " is not a palindrome.");
}
}
}
Output
#3) Reverse String Recursion Java
Given a string “Hello” we have to reverse it so that the resultant string is “olleH”.
This is done using recursion. Starting from the last character in the string we recursively print each character until all the characters in the string are exhausted.
The below program uses recursion to reverse a given string.
class String_Reverse
{
//recursive method to reverse a given string
void reverseString(String str)
{
//base condition; return if string is null or with 1 or less character
if ((str==null)||(str.length() <= 1))
System.out.println(str);
else
{
//recursively print each character in the string from the end
System.out.print(str.charAt(str.length()-1));
reverseString(str.substring(0,str.length()-1));
}
}
}
class Main{
public static void main(String[] args)
{
String inputstr = "SoftwareTestingHelp";
System.out.println("The given string: " + inputstr);
String_Reverse obj = new String_Reverse();
System.out.print("The reversed string: ");
obj.reverseString(inputstr);
}
}
Output
#4) Binary Search Java Recursion
A binary search algorithm is a famous algorithm for searching. In this algorithm, given a sorted array of n elements, we search this array for the given key element. In the beginning, we divide the array into two halves by finding the mid element of the array.
Then depending on whether the key < mid or key > mid we limit our search in the first or second half of the array. This way the same process is repeated until the location of the key elements is found.
We will implement this algorithm using recursion here.
import java.util.*;
class Binary_Search {
// recursive binary search
int binarySearch(int numArray[], int left, int right, int key) {
if (right >= left) {
//calculate mid of the array
int mid = left + (right - left) / 2;
// if the key is at mid, return mid
if (numArray[mid] == key)
return mid;
// if key < mid, recursively search the left subarray
if (numArray[mid] > key)
return binarySearch(numArray, left, mid - 1, key);
// Else recursively search in the right subarray
return binarySearch(numArray, mid + 1, right, key);
}
// no elements in the array, return -1
return -1;
}
}
class Main{
public static void main(String args[]) {
Binary_Search ob = new Binary_Search();
//declare and print the array
int numArray[] = { 4,6,12,16,22};
System.out.println("The given array : " + Arrays.toString(numArray));
int len = numArray.length; //length of the array
int key = 16; //key to be searched
int result = ob.binarySearch(numArray, 0, len - 1, key);
if (result == -1)
System.out.println("Element " + key + " not present");
else
System.out.println("Element " + key + " found at index " + result);
}
}
Output
#5) Find Minimum Value In Array Using Recursion
Using recursion we can also find the minimum value in the array.
The Java program to find the minimum value in the array is given below.
import java.util.*;
class Main
{
static int getMin(int numArray[], int i, int n)
{
//return first element if only one element or minimum of the array elements
return (n == 1) ? numArray[i] :
Math.min(numArray[i], getMin(numArray,i + 1 , n - 1));
}
public static void main(String[] args)
{
int numArray[] = { 7,32,64,2,10,23 };
System.out.println("Given Array : " + Arrays.toString(numArray));
int n = numArray.length;
System.out.print("Minimum element of array: " + getMin(numArray, 0, n) + "\n");
}
}
Output
These are some of the examples of recursion. Apart from these examples, a lot of other problems in the software can be implemented using recursive techniques.
Recursion Types
Recursion is of two types based on when the call is made to the recursive method.
They are:
#1) Tail Recursion
When the call to the recursive method is the last statement executed inside the recursive method, it is called “Tail Recursion”.
In tail recursion, the recursive call statement is usually executed along with the return statement of the method.
The general syntax for tail recursion is given below:
methodName ( T parameters…){
{
if (base_condition == true)
{
return result;
}
return methodName (T parameters …) //tail recursion
}
#2) Head Recursion
Head recursion is any recursive approach that is not a tail recursion. So even general recursion is ahead recursion.
Syntax of head recursion is as follows:
methodName (T parameters…){
if (some_condition == true)
{
return methodName (T parameters…);
}
return result;
}
Recursion Vs Iteration In Java
| Recursion | Iteration |
|---|---|
| Recursion is a process where a method calls itself repeatedly until a base condition is met. | Iteration is a process by which a piece of code is repeatedly executed for a finite number of times or until a condition is met. |
| Is the application for functions. | Is applicable for loops. |
| Works well for smaller code size. | Works well for larger code size. |
| Utilizes more memory as each recursive call is pushed to the stack | Comparatively less memory is used. |
| Difficult to debug and maintain | Easier to debug and maintain |
| Results in stack overflow if the base condition is not specified or not reached. | May execute infinitely but will ultimately stop execution with any memory errors |
| Time complexity is very high. | Time complexity is relatively on the lower side. |
Frequently Asked Questions
Q #1) How does Recursion work in Java?
Answer: In recursion, the recursive function calls itself repeatedly until a base condition is satisfied. The memory for the called function is pushed on to the stack at the top of the memory for the calling function. For each function call, a separate copy of local variables is made.
Q #2) Why is Recursion used?
Answer: Recursion is used to solve those problems that can be broken down into smaller ones and the entire problem can be expressed in terms of a smaller problem.
Recursion is also used for those problems that are too complex to be solved using an iterative approach. Besides the problems for which time complexity is not an issue, use recursion.
Q #3) What are the benefits of Recursion?
Answer:
The benefits of Recursion include:
- Recursion reduces redundant calling of function.
- Recursion allows us to solve problems easily when compared to the iterative approach.
Q #4) Which one is better – Recursion or Iteration?
Answer: Recursion makes repeated calls until the base function is reached. Thus there is a memory overhead as a memory for each function call is pushed on to the stack.
Iteration on the other hand does not have much memory overhead. Recursion execution is slower than the iterative approach. Recursion reduces the size of the code while the iterative approach makes the code large.
Q #5) What are the Advantages of Recursion over Iteration?
Answer:
- Recursion makes the code clearer and shorter.
- Recursion is better than the iterative approach for problems like the Tower of Hanoi, tree traversals, etc.
- As every function call has memory pushed on to the stack, Recursion uses more memory.
- Recursion performance is slower than the iterative approach.
Conclusion
Recursion is a very important concept in software irrespective of the programming language. Recursion is mostly used in solving data structure problems like towers of Hanoi, tree traversals, linked lists, etc. Though it takes more memory, recursion makes code simpler and clearer.
We have explored all about Recursion in this tutorial. We have also implemented numerous programming examples for a better understanding of the concept.
=> Read Through The Easy Java Training Series.