5.7 Recursion Depth, Repeated Work, and Tail Calls
Prerequisites: Recursion Base Case and Call Stack Estimated time: 35 minutes You are ready to continue when: You can calculate call depth, identify redundant subproblems, and explain the Java tail call boundary.
Active Call Depth Determines Stack Space Growth
At its deepest point, factorial(4) has five active factorial calls: 4, 3, 2, 1, 0. For input n, the active depth is O(n), so the conceptual auxiliary stack space is O(n). The exact number of bytes and the n that triggers StackOverflowError do not have a portable constant.
JIT may inline ordinary methods, but the Java language and JVM specification do not guarantee that any recursion can be converted to a constant stack. Do not use a machine experiment's "safe recursion depth" as a reference.
Naive Fibonacci Repeated Calculation
static long fibonacciSlow(int value) {
if (value < 0) {
throw new IllegalArgumentException("negative value");
}
if (value <= 1) {
return value;
}
return Math.addExact(fibonacciSlow(value - 1),
fibonacciSlow(value - 2));
}fibonacciSlow(5) computes fibonacciSlow(3) and fibonacciSlow(2) more than once. The call count grows exponentially, often written as an upper bound of O(2ⁿ); a tighter growth rate is related to the golden ratio. Do not claim in a tutorial that a certain n "definitely needs several seconds," as hardware, JIT, and implementation can change the time.
long also has an independent boundary: F(92) can be represented, but F(93) exceeds the signed long. Algorithm optimization will not expand the result type.
Memoization to Eliminate Redundant Subproblems
import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;
static BigInteger fibonacci(int value) {
if (value < 0) {
throw new IllegalArgumentException("negative value");
}
Map<Integer, BigInteger> cache = new HashMap<>();
cache.put(0, BigInteger.ZERO);
cache.put(1, BigInteger.ONE);
return fibonacci(value, cache);
}
static BigInteger fibonacci(int value,
Map<Integer, BigInteger> cache) {
BigInteger known = cache.get(value);
if (known != null) {
return known;
}
BigInteger result = fibonacci(value - 1, cache)
.add(fibonacci(value - 2, cache));
cache.put(value, result);
return result;
}Each n is computed exactly once, reducing the number of arithmetic operations to O(n), with O(n) cache entries and O(n) recursive frames. These counts do not imply O(n) total bytes. BigInteger avoids fixed-width overflow, but addition becomes more expensive as values grow. F(n) has Θ(n) bits, so caching the first n values uses Θ(n²) bits for the integers themselves. The iterative version retains a fixed number of integers, but their values also grow in size.
Caching within a single call avoids the infinite growth of a static mutable Map across requests and concurrency contention. In production scenarios, it's also necessary to set capacity, lifecycle, and key space boundaries.
The linear Fibonacci can be directly iterated, which is usually simpler:
static BigInteger fibonacciLoop(int value) {
if (value < 0) {
throw new IllegalArgumentException("negative value");
}
BigInteger previous = BigInteger.ZERO;
BigInteger current = BigInteger.ONE;
for (int index = 0; index < value; index++) {
BigInteger next = previous.add(current);
previous = current;
current = next;
}
return previous;
}Tail Recursion is a Syntax Position, Not a Java Optimization Guarantee
static long sumTail(int value, long accumulator) {
if (value < 0) {
throw new IllegalArgumentException("negative value");
}
if (value == 0) {
return accumulator;
}
return sumTail(value - 1,
Math.addExact(accumulator, value));
}A recursive call is the final action in the normal path of a method, referred to as the tail position. Implementations that support tail call elimination can reuse frames, but Java SE 17 does not require this behavior, and the common behavior of HotSpot cannot be considered a language guarantee. This Java method should still be evaluated with an O(n) stack depth.
Do not simplify the reason into some already removed or deprecated safety mechanism, nor say that C++ "definitely optimizes" when using -O2. Tail call optimization in C++ is also influenced by the compiler, ABI, debugging, and code shape. Language specifications such as Scheme have different guarantees for proper tail calls, and the contract must be checked on a per-language basis.
For linear tail recursion in Java, explicit loops are usually more reliable:
static long sumLoop(int value) {
if (value < 0) {
throw new IllegalArgumentException("negative value");
}
long result = 0L;
for (long current = 1; current <= value; current++) {
result = Math.addExact(result, current);
}
return result;
}The loop counter uses long so it cannot wrap when value == Integer.MAX_VALUE. Billions of iterations still make a poor unbounded service operation; callers need a workload limit.
An Explicit Stack Stores Pending Work on the Heap
Iterative DFS can use ArrayDeque to store nodes to be processed. It avoids the JVM call stack depth limit, but it's not "infinite": an explicit stack still occupies heap memory, and must handle capacity, duplicate nodes, and exceptions.
Professional Quick Reference
| Question | Conclusion |
|---|---|
| Recursion Stack | Calculated based on the maximum depth of simultaneous active calls |
| Naive Fibonacci | Exponential repetition; also constrained by the result type |
| Memoization | Eliminates duplicates but introduces cache, lifetime, and concurrency issues |
| Java Tail Recursion | The language/JVM does not guarantee constant stack optimization |
| Explicit Stack | Depth is moved to heap management, which does not represent unlimited resources |
| Performance Conclusion | Use input scale, complexity, and measurement, not fixed seconds |
Before Moving On
Draw the recurring subproblems in fibonacciSlow(5) and compare the cache, call depth, and cost of large integers between the memoized and iterative versions. Finally, explain three things: F(93) exceeds long, Java 17 does not guarantee tail call elimination, and explicit stacks merely shift resource pressure to the heap rather than providing infinite space.
The recursion tutorial ends here. The next page uses a set of complete experiments to review methods, overloading, and call stacks.