Recursion
Write methods that call themselves to walk trees and nested data, and know when the call stack limit means you should use a loop instead.
ReturnType solve(Input x) {
if (isBaseCase(x)) return simpleAnswer; // base case
return combine(solve(smaller(x))); // recursive case
}A recursive method calls itself on a smaller part of the problem. Every recursive method needs two things:
- A base case that returns without recursing: an empty list, a leaf node,
n == 0. - A recursive case that makes progress towards the base case, so the chain of calls ends.
Forget either and the method calls itself until the thread runs out of stack space, which ends in a StackOverflowError.
Where it fits in back-end code
Recursion shines on data that is shaped like a tree, because the code mirrors the data: product categories with subcategories, threaded comments with replies, nested JSON documents, an organisation chart, a directory of files. A method that handles one node and then calls itself for each child is usually shorter and clearer than the loop version.
For flat data, a loop is simpler. Summing a list or counting down from 10 recursively is a classroom exercise, not production code.
The call stack is the limit
Each call adds a frame to the current thread's stack, holding its parameters and local variables. The stack is small, typically 1 MB or 2 MB per platform thread by default on 64-bit systems, depending on the OS and CPU (set with -Xss), so depth is limited to somewhere in the thousands or tens of thousands of calls depending on frame size. Java does not perform tail-call optimisation, so writing the recursive call last does not help.
This decides when recursion is safe. A category tree five levels deep is fine. A linked chain of records, a recursive parser fed with input a client controls, or a walk over a deeply nested JSON body is not: an attacker can send a document nested 100,000 levels deep and crash the request thread. Either put a depth limit on the recursion, as JSON libraries do, or convert it to a loop with an explicit ArrayDeque as the stack, which lives on the heap and can grow much larger.
Repeated work
Some recursive definitions solve the same subproblem many times. The naive Fibonacci method makes an exponential number of calls. Storing results you have already computed (memoisation) turns it into linear work. Use an explicit get and put for the cache: calling HashMap.computeIfAbsent recursively modifies the map from inside its own mapping function, which can throw ConcurrentModificationException.
Example
When to use it
- Render a category menu of any depth from a tree loaded out of the database.
- Flatten a nested YAML or JSON configuration into dotted keys for environment overrides.
- Count all replies in a threaded comment tree, with a depth limit so a malicious payload cannot overflow the stack.
More examples
Flattening nested configuration
This is how nested YAML configuration becomes the dotted keys used in properties files and environment overrides. LinkedHashMap keeps the insertion order so the output is predictable.
void flatten(String prefix, Map<String, Object> node, Map<String, Object> out) {
for (Map.Entry<String, Object> entry : node.entrySet()) {
String key = prefix.isEmpty() ? entry.getKey() : prefix + "." + entry.getKey();
if (entry.getValue() instanceof Map<?, ?> child) {
@SuppressWarnings("unchecked")
Map<String, Object> nested = (Map<String, Object>) child;
flatten(key, nested, out); // recursive case: a nested section
} else {
out.put(key, entry.getValue()); // base case: a plain value
}
}
}
void main() {
Map<String, Object> pool = new LinkedHashMap<>();
pool.put("size", 10);
pool.put("timeoutMs", 3000);
Map<String, Object> db = new LinkedHashMap<>();
db.put("url", "jdbc:postgresql://localhost/shop");
db.put("pool", pool);
Map<String, Object> config = new LinkedHashMap<>();
config.put("port", 8080);
config.put("db", db);
Map<String, Object> flat = new LinkedHashMap<>();
flatten("", config, flat);
flat.forEach((k, v) -> IO.println(k + "=" + v));
}
// Output:
// port=8080
// db.url=jdbc:postgresql://localhost/shop
// db.pool.size=10
// db.pool.timeoutMs=3000Hitting the stack limit and the loop that avoids it
Ten million nested calls cannot fit on a thread's stack, while the loop uses constant space. Catching StackOverflowError here is only for the demonstration; in real code, prevent it rather than catch it.
long sumRecursive(long n) {
if (n == 0) {
return 0;
}
return n + sumRecursive(n - 1); // one stack frame per number
}
long sumIterative(long n) {
long total = 0;
for (long i = 1; i <= n; i++) {
total += i;
}
return total;
}
void main() {
IO.println(sumRecursive(1_000));
try {
sumRecursive(10_000_000);
} catch (StackOverflowError e) {
IO.println("recursive version: StackOverflowError");
}
IO.println(sumIterative(10_000_000));
}
// Output:
// 500500
// recursive version: StackOverflowError
// 50000005000000Memoisation to avoid repeated work
Without the cache, fib(50) would make billions of calls; with it, each value is computed once. The cache uses get and put because a recursive call inside HashMap.computeIfAbsent changes the map during the computation, which can throw ConcurrentModificationException.
final Map<Integer, Long> cache = new HashMap<>();
int calls = 0;
long fib(int n) {
calls++;
if (n < 2) {
return n;
}
Long known = cache.get(n);
if (known != null) {
return known;
}
long result = fib(n - 1) + fib(n - 2);
cache.put(n, result); // plain put, not computeIfAbsent
return result;
}
void main() {
IO.println(fib(50));
IO.println("calls: " + calls);
IO.println(fib(90));
}
// Output:
// 12586269025
// calls: 99
// 2880067194370816120
Discussion