Recursion in Java is a technique where a method calls itself to solve a smaller copy of the same problem, until it reaches a case simple enough to answer without another call, called the base case. Each call waits for the result of the smaller call and builds its own result from it.
Recursion fits problems that contain smaller versions of themselves, such as trees, nested folders, nested JSON, permutations and divide-and-conquer algorithms like merge sort and quicksort. For simple counting loops, a for loop is clearer and safer.
The following example computes a factorial recursively. The method stops at n <= 1, and every other call multiplies n with the factorial of n – 1.
static long factorial(int n) {
if (n < 0) {
throw new IllegalArgumentException("n must not be negative");
}
if (n <= 1) {
return 1; // base case
}
return n * factorial(n - 1); // recursive case
}long f4 = factorial(4); // 24
long f20 = factorial(20); // 2432902008176640000
long f0 = factorial(0); // 1Every recursive method needs both parts, the base case and the recursive case. We look at how the call stack runs a recursive method, write recursion for real tasks, fix the slow Fibonacci with memoization, and see when recursion ends in a StackOverflowError.
1. Base Case and Recursive Case
A recursive method has two kinds of branches. The base case returns a result without calling the method again, and it is what stops the recursion. The recursive case calls the method with a smaller input, so every call gets closer to the base case.
- For factorial(n), the base case is n <= 1, and the recursive case reduces n by one.
- For a folder tree, the base case is a file, and the recursive case visits each subfolder.
- For a string, the base case is the empty string, and the recursive case works on the string without its first character.
If the input does not move toward the base case, the method calls itself until the thread runs out of stack memory and throws StackOverflowError. That is why factorial() rejects negative numbers instead of recursing forever on -1, -2 and so on.
2. How Recursion Uses the Call Stack
Every method call in Java gets a stack frame on the thread’s call stack. The frame holds the method’s parameters and local variables, so each recursive call has its own copy of n. A frame is removed when its method returns.
When we call factorial(4), the JVM pushes frames for factorial(4), factorial(3), factorial(2) and factorial(1). The last call hits the base case and returns 1, and the waiting frames multiply and return one after another, giving 2, 6 and 24.
Recursion depth is therefore limited by the size of the thread stack, which is 1 MB by default on 64-bit Linux and macOS. On our Java 25 machine, a simple recursive sum overflowed at around 10,000 calls, and an empty recursive method reached between 10,000 and 23,000 calls. The exact depth varies between runs, because the JIT compiler changes the size of each frame once it compiles the method.
3. Recursion Examples in Java
Three small programs cover the typical shapes of recursive methods, from a single recursive call to calls that branch.
3.1. Reversing a String
A string reversed is its last part reversed, followed by its first character. The empty string is the base case.
static String reverse(String s) {
if (s == null || s.isEmpty()) {
return s;
}
return reverse(s.substring(1)) + s.charAt(0);
}String reversed = reverse("java"); // "avaj"
String empty = reverse(""); // ""Each call creates a new substring, so the method is O(n2) in time and memory, and it splits emoji and other characters stored as two char values. For real code, new StringBuilder(s).reverse() is the better choice, because it keeps those pairs together.
3.2. Recursive Binary Search
Binary search halves a sorted array in every step, so each call works on half of the previous range, which suits recursion well. The base case is an empty range, which means the value is missing.
static int binarySearch(int[] a, int key, int low, int high) {
if (low > high) {
return -1; // not found
}
int mid = low + (high - low) / 2;
if (a[mid] == key) {
return mid;
}
return a[mid] < key
? binarySearch(a, key, mid + 1, high)
: binarySearch(a, key, low, mid - 1);
}int[] years = {2015, 2018, 2020, 2023, 2026};
int found = binarySearch(years, 2023, 0, years.length - 1); // 3
int missing = binarySearch(years, 2019, 0, years.length - 1); // -1The recursion depth is only about log2(n), so even an array of one billion elements needs about 30 calls. Recursion is safe whenever the depth grows that slowly.
3.3. Walking a Tree of Categories
Recursion helps most with trees. A shop menu has categories, and each category can contain items and subcategories of any depth. Counting all items needs one recursive call per subcategory.
record Category(String name, int items, List<Category> children) {}static int countItems(Category c) {
int total = c.items();
for (Category child : c.children()) {
total += countItems(child);
}
return total;
}Category menu = new Category("Menu", 0, List.of(
new Category("Drinks", 2, List.of(new Category("Tea", 3, List.of()), new Category("Juice", 4, List.of()))),
new Category("Snacks", 5, List.of())));
int allItems = countItems(menu); // 14A category without children is the base case, because the loop body never runs and the method returns its own count. For folders on disk, Files.walk() already does this traversal for us without recursion in our code.
4. Fibonacci and Memoization
Some recursive methods call themselves twice. The Fibonacci number fib(n) is fib(n – 1) + fib(n – 2), which looks elegant but repeats the same work again and again.
static long fib(int n) {
if (n < 2) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
On Java 25, fib(30) made 2,692,537 calls in a few milliseconds, but fib(40) needed 331,160,281 calls and about 0.7 seconds, because the number of calls grows exponentially, by a factor of about 1.6 per step. Memoization fixes it by storing each result the first time we compute it.
static long fibMemo(int n, Map<Integer, Long> memo) {
if (n < 2) {
return n;
}
Long cached = memo.get(n);
if (cached != null) {
return cached;
}
long value = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
memo.put(n, value);
return value;
}long fib30 = fib(30); // 832040
long fib90 = fibMemo(90, new HashMap<>()); // 2880067194370816120With memoization, each value from 0 to 90 is computed once, so fibMemo(90) returns in microseconds, whereas the naive version would need more than 1018 calls.
5. Types of Recursion
Recursive methods are grouped by where and how often they call themselves.
| Type | What it means | Example |
|---|---|---|
| Direct recursion | The method calls itself | factorial() |
| Indirect recursion | Method A calls B, and B calls A | isEven() and isOdd() |
| Tail recursion | The recursive call is the last action | A sum with an accumulator parameter |
| Non-tail recursion | Work happens after the recursive call returns | n * factorial(n – 1) |
| Tree recursion | The method calls itself more than once | fib(n – 1) + fib(n – 2) |
Indirect recursion needs a base case on each side. The methods isEven() and isOdd() call each other for a non-negative number, and both stop at 0.
static boolean isEven(int n) {
return n == 0 || isOdd(n - 1);
}
static boolean isOdd(int n) {
return n != 0 && isEven(n - 1);
}boolean even = isEven(10); // true
boolean odd = isOdd(7); // trueTail recursion matters in languages that turn it into a loop. Java does not, which the tail recursion vs non-tail recursion article explains with a trampoline workaround.
6. Recursion vs Iteration
Every recursive method can be rewritten as a loop, sometimes with an explicit stack. The time complexity is the same, so the choice depends on readability and depth.
| Aspect | Recursion | Iteration |
|---|---|---|
| Code for trees and nested data | Short and natural | Needs an explicit stack or queue |
| Code for counting and summing | Longer, with more room for a wrong base case | Short and clear |
| Memory | One stack frame per active call | Constant, or a heap-based stack |
| Depth limit | Thread stack size, around 10,000 frames by default | Only the heap |
| Speed | Small overhead per call | Slightly faster |
A good rule is to use recursion when the depth grows like log n or follows the shape of a tree, and to use a loop when the depth grows with n, such as walking a list of one million elements.
7. Recursion FAQs
Base cases, stack depth and speed cause the most confusion with recursion.
7.1. What happens if a recursive method has no base case?
The method keeps calling itself until the thread stack is full, and the JVM throws StackOverflowError. The error is not a checked exception, and catching it is not a fix, because the program state is often unusable afterwards.
7.2. How do we increase the recursion depth in Java?
We start the JVM with a larger stack, such as java -Xss8m App, which applies to every new thread. A larger stack only moves the limit, so rewriting deep recursion as a loop, as the tail recursion tutorial shows, is the more reliable fix.
7.3. Is recursion slower than a loop in Java?
Slightly, because each call creates a stack frame, but the difference is small next to the algorithm’s complexity. The naive Fibonacci is slow because of its O(2n) calls, not because recursion is slow.
7.4. Can recursion be replaced by streams in Java?
For flat data, yes. Summing or filtering a list is clearer with IntStream or Stream than with recursion. For nested data such as trees, recursion stays the simpler choice, and Stream.flatMap() can call a recursive method to flatten the tree.
8. Conclusion
A recursive method solves a problem by calling itself on a smaller input until it reaches a base case. Each call gets its own stack frame, so the depth of recursion is limited by the thread stack, and a missing or unreachable base case ends in StackOverflowError.
Recursion fits trees, nested data and divide-and-conquer algorithms, where the depth stays small. Methods that call themselves more than once need memoization, and deep linear recursion is better written as a loop.
9. References
- JVM Specification, Java Virtual Machine Stacks
- StackOverflowError (Java SE 25 API)
- The java command, -Xss option
Happy Learning !!
