Recursion in Java
Subject: Data Structures and Algorithms · Language: Java · Level: beginner · 6 min read
Learn recursive methods, base case, recursive case, call stack, factorial, and DSA recursion basics.
Recursion means a method calls itself to solve a problem. Instead of solving the complete problem in one step, recursion solves a smaller version of the same problem and uses that result to build the final answer. A recursive solution is useful when the problem naturally repeats the same pattern. For example, factorial, tree traversal, directory traversal, backtracking, and divide-and-conquer problems all have a repeated smaller structure.
For beginners, recursion may feel difficult because the method call is not finished immediately. Java keeps each unfinished method call in memory until the smallest case is reached, and then the answers return step by step.
Base Case
The base case is the stopping condition of recursion. It tells the method when the problem has become small enough to answer directly. Without a correct base case, the method keeps calling itself again and again. This can crash the program with a stack overflow error because too many method calls remain pending in memory.
Recursive Case
The recursive case is the part where the method calls itself with a smaller or simpler input. This smaller input must move toward the base case. For example, in factorial, `factorial(n)` calls `factorial(n - 1)`. The value of `n` keeps decreasing, so it will eventually reach `1` or `0`, where the base case can stop recursion.
Call Stack
The call stack is the memory area where Java keeps track of active method calls. Every recursive call is placed on the stack until it finishes. When the base case returns an answer, Java starts completing the pending calls in reverse order. This is why recursion is closely connected with stack behavior.
A student should remember this simple idea: recursion goes down by making smaller calls, and then comes back up by returning answers.
Recursion vs Loop
Both recursion and loops can repeat work. A loop repeats using conditions such as `for` or `while`, while recursion repeats by calling the same method again. Use recursion when the problem is easier to express as smaller versions of itself, such as tree traversal or backtracking. Use loops when simple repetition is clearer, such as printing numbers or adding array elements.
Factorial Example
Factorial of 5 means `5 * 4 * 3 * 2 * 1`, which is 120. Using recursion, `factorial(n)` can be written as `n * factorial(n - 1)`. Here, the base case is `factorial(0)` or `factorial(1)`, which returns `1`. The recursive case multiplies `n` with the factorial of the smaller number.
Where Recursion Is Used in DSA
Recursion is used in tree traversal, graph DFS, backtracking, divide and conquer, binary search, merge sort, quick sort, and dynamic programming. Many advanced DSA topics become easier when recursion is clear. That is why students should learn recursion slowly and focus on base case, recursive case, and return value.
Example Program
```java
import java.util.*;
public class Main {
static int factorial(int n) {
if (n == 0 || n == 1) {
return 1;
}
return n * factorial(n - 1);
} public static void main(String[] args) {
Scanner sc = new Scanner(System.in); System.out.print("Enter n: ");
int n = sc.nextInt(); System.out.println("Factorial = " + factorial(n));
}
}
```
Practice Question
Write a recursive method to calculate the sum of numbers from 1 to n.