Introduction to Java Recursion
Recursion is a special technique where a method solves a problem by calling itself. You don’t need to write repetitive loops or manually break a problem into steps, because recursion allows the problem to be divided into smaller, more manageable sub-problems, and each solved using the same method.
In simple words, recursion is especially useful for problems that have a repeating or self-similar structure, such as calculating factorials, traversing trees, or solving puzzles.
Components of Recursion in Java
Every recursive method requires two essential parts:
- Base Case: This is a stopping condition that prevents the method from calling itself indefinitely. Without a base case, recursion can lead to a stack overflow error.
- Recursive Case: This is the part where the method calls itself with a smaller or simpler input. It moves the problem closer to the base case.
Example of Recursion: Factorial Calculation
Let’s understand the simple code example of recursion.
public class RecursionExample {
// Recursive method to calculate factorial
public static int factorial(int n) {
if (n == 0 || n == 1) { // Base case
return 1;
} else { // Recursive case
return n * factorial(n - 1);
}
}
public static void main(String[] args) {
int number = 5;
System.out.println("Factorial of " + number + " is: " + factorial(number));
}
}
Output:
Factorial of 5 is: 120Explanation of this code:
- The method factorial calls itself with n-1 until it reaches the base case (n == 0 or n == 1).
- Once the base case is reached, the recursive calls start returning values, and the final factorial is calculated.
Why Use Recursion In Java?
- It simplifies complex problems and makes the code easier to read and understand.
- Reduce the repetitive code like multiple loops or manual calculations.
- It’s is useful for Fibonacci numbers, and combinatorial problems.
Types of Recursion In Java
In Java, recursion can happen in two main ways: Direct Recursion and Indirect Recursion.
a) Direct Recursion
In direct recursion, a method calls itself directly to solve a problem. This is the most common form of recursion. Each time the method calls itself, it works on a smaller part of the problem until it reaches a base case, which stops further calls.
For example:
public class DirectRecursionExample {
static void countdown(int number) {
if (number == 0) { // Base case to stop recursion
System.out.println("Blast off!");
return;
}
System.out.println("Counting down: " + number);
countdown(number - 1); // Directly calling itself
}
public static void main(String[] args) {
countdown(5);
}
}
Output:
Counting down: 5
Counting down: 4
Counting down: 3
Counting down: 2
Counting down: 1
Blast off!Explanation of this code:
- Here, the countdown() method directly calls itself, and each call prints the number and then decreases it by 1. Once it reaches 0, the base case stops further recursion.
b) Indirect Recursion
In indirect recursion is a method that does not call itself directly. Instead, it calls another method, and that second method calls the first one again, creating a loop of recursive calls between two or more methods.
Example code:
public class IndirectRecursionExample {
static void methodA(int number) {
if (number > 0) {
System.out.println("Method A: " + number);
methodB(number - 1); // Calls methodB
}
}
static void methodB(int number) {
if (number > 0) {
System.out.println("Method B: " + number);
methodA(number - 1); // Calls methodA again
}
}
public static void main(String[] args) {
methodA(3); // Starts the indirect recursion
}
}
Output:
Method A: 3
Method B: 2
Method A: 1
Method B: 0- Here, methodA() calls methodB(), and then methodB() calls methodA() again. This process continues until the number becomes 0.
Examples of Recursion in Java
Let’s understand how recursion actually works with some easy and practical examples.
1) Factorial Calculation
The factorial of a number n (written as n!) means:
n × (n-1) × (n-2) × … × 1
For example,
5! = 5 × 4 × 3 × 2 × 1 = 120
public class FactorialExample {
// Recursive method to find factorial
public static int factorial(int n) {
if (n == 0) { // Base case: stops recursion
return 1;
}
return n * factorial(n - 1); // Recursive call
}
public static void main(String[] args) {
int number = 5;
System.out.println("Factorial of " + number + " is: " + factorial(number));
}
}
Output:
Factorial of 5 is: 120
- In this code, the method keeps calling itself with a smaller number (n-1) until it reaches 0.
2) Fibonacci Series
The Fibonacci Series is a pattern where each number is the sum of the two previous numbers.
Formula of Fibonacci Series:
F(n) = F(n-1) + F(n-2)
with F(0) = 0 and F(1) = 1
So, the sequence looks like this pattern:
0, 1, 1, 2, 3, 5, 8, 13…
public class FibonacciExample {
// Recursive method for Fibonacci
public static int fibonacci(int n) {
if (n == 0) return 0; // Base case 1
if (n == 1) return 1; // Base case 2
return fibonacci(n - 1) + fibonacci(n - 2); // Recursive case
}
public static void main(String[] args) {
int terms = 7;
System.out.println("Fibonacci series up to " + terms + " terms:");
for (int i = 0; i < terms; i++) {
System.out.print(fibonacci(i) + " ");
}
}
}
Output:
Fibonacci series up to 7 terms:
0 1 1 2 3 5 8
- Each recursive call depends on the two previous results.
- The method continues until it hits the base cases (0 and 1), then adds results backward.
3) Sum of Natural Numbers
The sum of the first n natural numbers means:
1 + 2 + 3 + … + n
For example, sum of first 5 numbers = 15.
public class SumExample {
// Recursive method to find sum of numbers
public static int sum(int n) {
if (n == 0) { // Base case
return 0;
}
return n + sum(n - 1); // Recursive case
}
public static void main(String[] args) {
int num = 10;
System.out.println("Sum of first " + num + " natural numbers: " + sum(num));
}
}
Output:
Sum of first 10 natural numbers: 55
4) Binary Search (Recursive Implementation)
Binary Search is a fast searching technique used with sorted arrays. It repeatedly divides the array into two halves to find the target element.
public class BinarySearchExample {
// Recursive method for binary search
public static int binarySearch(int[] arr, int low, int high, int target) {
if (low > high) {
return -1; // Base case: element not found
}
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
return mid; // Base case: element found
}
else if (arr[mid] > target) {
return binarySearch(arr, low, mid - 1, target); // Search left half
}
else {
return binarySearch(arr, mid + 1, high, target); // Search right half
}
}
public static void main(String[] args) {
int[] numbers = {2, 4, 6, 8, 10, 12};
int target = 10;
int index = binarySearch(numbers, 0, numbers.length - 1, target);
if (index != -1) {
System.out.println("Element found at index: " + index);
} else {
System.out.println("Element not found.");
}
}
}
Output:
Element found at index: 4
In this code, recursion divides the array each time. If the middle element isn’t the target, the search continues on either the left or right half, until it finds the element or finishes searching.