Recursion is one of the most powerful—and most misunderstood—concepts in Java programming.
In this tutorial, we will break down exactly how recursive methods work, why we use them, and dive into 12 practical code examples to completely solidify your understanding.
What is Recursion in Java?
Recursion in Java is a programming technique where a method calls itself to solve a smaller instance of the same problem. Every recursive method requires two core components: a base case to stop execution and prevent infinite loops, and a recursive call that moves step-by-step toward the base case.
How Does Recursion Work? The 2 Golden Rules
Before diving into the code, it is crucial to understand that every recursive method is built on two strict rules. If you miss either of these, your program will run infinitely and crash with a StackOverflowError.
1. The Base Case (When to Stop)
This is the terminating condition. It tells the method when to stop calling itself and start returning values back to the program. Think of it as the bottom of the staircase.
2. The Recursive Step (The Work)
This is where the method actually calls itself. However, every time it calls itself, the input parameters must change to move one step closer to the Base Case.
When a method calls itself, Java pauses the current method and waits for the new one to finish. Let’s look at a visual example of how these recursive calls chain together step-by-step to reach the base case.
🐛 Spot the Bug: Prevent the Crash
The following code compiles perfectly, but it throws a StackOverflowError when we call countDown(5). Can you spot which Golden Rule was broken?
if (n == 0) {
System.out.println(“Done!”);
return;
}
System.out.println(n);
countDown(n); // recursive call
}
👉 Click here to reveal the Bug & The Fix
Because we called
countDown(n) instead of countDown(n - 1), the method never steps closer to the base case (0). It will endlessly print “5” until memory runs out.The Fix: Change line 7 to
countDown(n - 1);🚀 Need help mastering Recursion?
While recursion can be a tricky concept, it is an essential skill for any Java developer. If you are struggling with complex coding logic, an Online Java Tutor can help. I provide personalized, 1-on-1 training to help you confidently write both basic and advanced Java code.
🥞 Visualizing the Memory Stack (LIFO)
The Call Stack operates on a Last-In, First-Out (LIFO) principle. When you run factorial(3), Java doesn’t instantly know the answer. It has to pause the current method and push the next method on top of the stack until it finally hits the base case.
1️⃣ Click to watch the Stack BUILD (Push)
Top of Stack (Executes First)
Bottom of Stack
2️⃣ Click to watch the Stack RESOLVE (Pop)
📉 Top pops off:
factorial(1) returns 1.📉 Middle pops off:
factorial(2) computes 2 * 1 and returns 2.📉 Bottom pops off:
factorial(3) computes 3 * 2 and returns 6.The final output returned to your main method is 6.
12 Examples of Recursion in Java
- Factorial of a Number Using Recursion
- Fibonacci Series using Recursion
- Using Java Recursion to Reverse a given String
- Check if a given string is a Palindrome using Recursion
- Find minimum number in an int array using Java Recursion
- Find the number of odd numbers in an int array using Recursion
- Find the largest even int in an int array using Recursion
- Find the sum of numbers larger then a number in an int array using Recursion
- Find the Greatest Common Divisor (GCD) using Recursion
- Implement Binary Search using Recursion
- Decimal to Binary Conversion using Java Recursion
- Generate All Subsets of a String using Recursion
1. Factorial of a Number Using Recursion
public class Factorial {
public static int factorial(int n) {
if (n != 0) // ending condition
return n * factorial(n - 1); // recursive call
else
return 1;
}
public static void main(String[] args) {
int num = 7;
int fact = factorial(num);
System.out.println("Factorial of the number " + num + " is " + fact);
}
}Output -> Factorial of the number 7 is 5040
2. Fibonacci Series using Recursion
public class Fibanoccai {
public static int fibonacci(int x) {
if (x == 0) {
return 0;
}
if (x == 1 || x == 2) {
return 1;
}
return fibonacci(x - 2) + fibonacci(x - 1);
}
public static void main(String[] args) {
int maxNumber = 10;
System.out.print("Fibonacci Series of " + maxNumber + " numbers: ");
for (int i = 0; i < maxNumber; i++) {
System.out.print(fibonacci(i) + " ");
}
}
}Output -> Fibonacci Series of 10 numbers: 0 1 1 2 3 5 8 13 21 34
3. Using Java Recursion to Reverse a given String
class StringReverse {
// recursive method to reverse a given string
void reverseString(String str) {
// base condition
if ((str == null) || (str.length() <= 1)) {
System.out.println(str);
} else {
System.out.print(str.charAt(str.length() - 1));
reverseString(str.substring(0, str.length() - 1));
}
}
}
public class Main {
public static void main(String[] args) {
String input = "JavaTutorOnline";
System.out.println("The given string: " + input);
StringReverse obj = new StringReverse();
System.out.print("The reversed string: ");
obj.reverseString(input);
}
}Output
The given string: JavaTutorOnline
The reversed string: enilnOrotuTavaJ
4. Check if a given string is a Palindrome using Recursion
public class Palindrome {
public static boolean checkPalindrome(String s) {
if (s.length() == 0 || s.length() == 1) {
return true;
}
if (s.charAt(0) == s.charAt(s.length() - 1)) {
return checkPalindrome(s.substring(1, s.length() - 1));
}
return false;
}
public static void main(String[] args) {
String s1 = "MADAM";
boolean b1 = checkPalindrome(s1);
if (b1 == true) {
System.out.println("The String \"" + s1 + "\" is a Palindrome");
} else {
System.out.println("The String \"" + s1 + "\" is not a Palindrome");
}
}
}Output -> The String “MADAM” is a Palindrome
5. Find minimum number in an int array using Java Recursion
// Function to find the minimum number in an array
public static int findMin(int[] numbers, int startIndex, int endIndex) {
// If size = 0 means whole array has been traversed
if (startIndex == endIndex) {
return numbers[startIndex]; // stopping condition
}
return Math.min(numbers[endIndex], findMin(numbers, startIndex, endIndex - 1));
}6. Find the number of odd numbers in an int array using Recursion
// Function to find number of odd integers
public static int countOddNumbers(int[] elements, int startIndex, int endIndex) {
int count = 0;
if (startIndex == endIndex) { // stopping condition
if (elements[startIndex] % 2 == 0) {
count = count + 0;
} else {
count = count + 1;
}
return count;
} else {
if (elements[endIndex] % 2 == 0) {
count = count + 0;
} else {
count = count + 1;
}
int i = countOddNumbers(elements, startIndex, endIndex - 1) + count;
return i;
}
}7. Find the largest even int in an int array using Recursion
// Function to find the largest even int
public static int computeLargestEven(int[] elements, int startIndex, int endIndex) {
int largest = 0;
if (startIndex == endIndex) {
if (elements[startIndex] % 2 == 0) {
largest = elements[startIndex];
}
return largest;
} else {
if (elements[endIndex] % 2 == 0) {
return Math.max(elements[endIndex], computeLargestEven(elements, startIndex, endIndex - 1));
} else {
return Math.max(0, computeLargestEven(elements, startIndex, endIndex - 1));
}
}
}8. Find the sum of numbers larger then a number in an int array using Recursion
// Function to find the sum of numbers larger than the first
public static int sumOfNumbersLargerThanFirst(int[] elements, int startIndex, int endIndex, int firstNumber) {
int count = 0;
if (startIndex == endIndex) {
if (elements[startIndex] > firstNumber) {
count = count + elements[startIndex];
}
return count;
} else {
if (elements[endIndex] > firstNumber) {
count = count + elements[endIndex];
}
count = count + sumOfNumbersLargerThanFirst(elements, startIndex, endIndex - 1, firstNumber);
return count;
}
}9. Find the Greatest Common Divisor (GCD) using Recursion
public class GCDExample {
public static int gcd(int a, int b) {
if (b == 0) {
return a; // Base case
}
return gcd(b, a % b); // Recursive case
}
public static void main(String[] args) {
int a = 48, b = 18; // Example input
System.out.println("GCD of " + a + " and " + b + " is: " + gcd(a, b));
}
}10. Implement Binary Search using Recursion
public class BinarySearchExample {
public static int binarySearch(int[] arr, int left, int right, int target) {
if (right >= left) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid; // Base case: target found
}
if (arr[mid] > target) {
return binarySearch(arr, left, mid - 1, target); // Search in left half
}
return binarySearch(arr, mid + 1, right, target); // Search in right half
}
return -1; // Target not found
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5}; // Example input
int target = 3;
int result = binarySearch(arr, 0, arr.length - 1, target);
System.out.println("Element found at index: " + result);
}
}11. Decimal to Binary Conversion using Java Recursion
public class DecimalToBinary {
public static void toBinary(int n) {
if (n == 0) {
return; // Base case
}
toBinary(n / 2); // Recursive call
System.out.print(n % 2); // Print binary digits
}
public static void main(String[] args) {
int number = 10;
System.out.print("Binary of " + number + " is: ");
toBinary(number);
}
}12. Generate All Subsets of a String using Recursion
public class StringSubsets {
public static void generateSubsets(String str, String current, int index) {
if (index == str.length()) { // Base case
System.out.println(current);
return;
}
generateSubsets(str, current, index + 1); // Exclude current character
generateSubsets(str, current + str.charAt(index), index + 1); // Include current character
}
public static void main(String[] args) {
String str = "abc";
generateSubsets(str, "", 0);
}
}Main function to call the recursive methods
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Recursive {
public static void main(String[] args) {
int[] arr = new int[100];
InputStreamReader isr = new InputStreamReader(System.in);
// System.in is a standard input stream object connected with the keyboard
BufferedReader br = new BufferedReader(isr);
String sr = null;
int i = 0; // Will keep track of how many ints have been entered through the keyboard
do {
try {
sr = br.readLine();
arr[i] = Integer.parseInt(sr);
i++;
} catch (IOException e) {
e.printStackTrace();
}
} while (!sr.equals("0"));
// The array has been populated with values and 'i' is storing the number of inputs
// Calling function to find minimum number
int min = findMin(arr, 0, i - 1);
System.out.println("The minimum number is " + min);
// Calling function to find number of odd integers
int o = countOddNumbers(arr, 0, i - 1);
System.out.println("The count of odd integers in the sequence is " + o);
// Calling function to find the largest even int
int lE = computeLargestEven(arr, 0, i - 1);
System.out.println("The largest even integer in the sequence is " + lE);
// Calling function to find the sum of numbers larger than the first
int sum = sumOfNumbersLargerThanFirst(arr, 0, i - 1, arr[0]);
System.out.println("The sum of numbers larger than the first is " + sum);
}
}Frequently Asked Questions on Java Recursion
What is a base case in Java recursion?
A base case is the condition that stops the recursive method from calling itself infinitely. Without a base case, a recursive function will cause a StackOverflowError as it exhausts the Java Virtual Machine’s stack memory.
Why does my recursive Java program throw a StackOverflowError?
A StackOverflowError in Java usually occurs because the recursive method lacks a reachable base case, or the recursive step is not moving closer to the base case, causing infinite recursion.
Which is faster in Java, recursion or iteration?
Iteration (loops) is generally faster and uses less memory in Java than recursion. Recursion adds overhead because every method call pushes a new frame onto the call stack. However, recursion is often preferred for complex data structures like trees and graphs due to cleaner, more readable code.
This blog post really clarified the concept of recursion for me! The example program was easy to follow and helped solidify my understanding. I appreciate the detailed explanation of each step. Thank you for sharing such valuable insights!