Tail recursion is a form of recursion where the recursive call is the very last action of the method, so nothing is left to compute after the call returns. In non-tail recursion, the method still has work to do with the result, such as adding or multiplying it.
Compilers for some languages turn tail recursion into a loop, which removes the risk of running out of stack. Java does not, so in Java we use tail recursion mostly as a step toward a loop, or together with a trampoline when we want to keep the recursive style.
The following example writes the same sum in both styles. Both return the right result for 1,000, and both fail for a large input on a default thread stack.
static long sum(int n) {
return n == 0 ? 0 : n + sum(n - 1); // non-tail: adds after the call
}
static long sumTail(int n, long acc) {
return n == 0 ? acc : sumTail(n - 1, acc + n); // tail: the call is the last action
}long a = sum(1_000); // 500500
long b = sumTail(1_000, 0); // 500500
long c = sum(100_000); // StackOverflowError
long d = sumTail(100_000, 0); // StackOverflowErrorNotice that the tail version carries the running total in an extra parameter called an accumulator. We look at how to spot and write tail calls, why the JVM does not optimize them, and the two working alternatives in Java, a loop and a trampoline.
1. Tail vs Non-Tail Recursion
A call is a tail call when the method returns the call’s result unchanged. In n + sum(n – 1), the method still adds n after sum() returns, so the call is not in tail position. In sumTail(n – 1, acc + n), the addition happens before the call, and the method only passes the result through.
A quick test is to ask what the method does with the value it gets back. If it returns it as it is, the call is a tail call.
| Code | Tail call? | Why |
|---|---|---|
| return n * factorial(n – 1); | No | Multiplies after the call |
| return factorial(n – 1, acc * n); | Yes | Returns the result as it is |
| return fib(n – 1) + fib(n – 2); | No | Adds two results |
For void methods, the same test asks whether any statement runs after the recursive call. The two methods print the same numbers in opposite orders.
static void countDown(int n, List<Integer> out) {
if (n == 0) {
return;
}
out.add(n);
countDown(n - 1, out); // tail call, nothing runs after it
}
static void countUp(int n, List<Integer> out) {
if (n == 0) {
return;
}
countUp(n - 1, out); // not a tail call
out.add(n); // runs while the frames return
}List<Integer> down = new ArrayList<>();
countDown(3, down);
List<Integer> descending = down; // [3, 2, 1]
List<Integer> up = new ArrayList<>();
countUp(3, up);
List<Integer> ascending = up; // [1, 2, 3]The countUp() method is called head recursion, because the recursive call comes first and the work comes after it. Its numbers come out in ascending order, which shows that the work runs while the frames return.
2. Converting Non-Tail Recursion to Tail Recursion
We make a method tail-recursive by moving the pending work into parameters. The accumulator carries the partial result down the calls, so the base case can return the final answer.
2.1. Factorial with an Accumulator
The non-tail factorial multiplies on the way back. The tail version multiplies on the way down and starts the accumulator at 1.
static long factorialTail(int n, long acc) {
if (n < 0) {
throw new IllegalArgumentException("n must not be negative");
}
return n <= 1 ? acc : factorialTail(n - 1, acc * n);
}long f5 = factorialTail(5, 1); // 120
long f20 = factorialTail(20, 1); // 2432902008176640000A long holds factorials up to 20, and factorialTail(21, 1) overflows to a negative number. For larger values, the accumulator becomes a BigInteger.
2.2. Fibonacci with Two Accumulators
Tree recursion, such as fib(n – 1) + fib(n – 2), needs two results, so one accumulator is not enough. We keep the last two Fibonacci numbers as parameters, which also turns the O(2n) method into an O(n) method.
static long fibTail(int n, long previous, long current) {
return n == 0 ? previous : fibTail(n - 1, current, previous + current);
}long fib10 = fibTail(10, 0, 1); // 55
long fib50 = fibTail(50, 0, 1); // 12586269025Not every tree recursion converts with so little code. Walking a tree visits several children, and making that tail-recursive needs an explicit stack or continuation-passing style, which is harder to read than the plain recursive version.
3. Does Java Optimize Tail Recursion?
No. Neither the javac compiler nor the HotSpot JVM removes tail calls, so a tail-recursive method uses one stack frame per call, the same as a non-tail one. Our sumTail(100_000, 0) call in the intro proves it, because it throws StackOverflowError with the default 1 MB stack on Java 25.
The JVM keeps every frame for two reasons. Stack traces show each call, which developers rely on for debugging, and parts of the Java platform inspect the call stack, so the JVM cannot drop frames. Project Loom discussed explicit tail calls, but its wiki states that automatic tail-call optimization is not a goal, and Loom shipped virtual threads instead.
Kotlin and Scala solve it in their compilers, which turn a self-recursive tail call into a loop in the bytecode.
- In Kotlin, the tailrec modifier tells the compiler to rewrite the function as a loop, and it warns when the call is not in tail position.
- In Scala, the @tailrec annotation makes the compiler fail when it cannot rewrite the method.
4. Turning Tail Recursion into a Loop
A tail-recursive method converts into a loop mechanically. The parameters become local variables, the recursive call becomes an assignment of the new values, and the base case becomes the loop condition.
static long sumLoop(int n) {
long acc = 0;
while (n != 0) { // base case as the loop condition
acc = acc + n; // same as sumTail(n - 1, acc + n)
n = n - 1;
}
return acc;
}long big = sumLoop(100_000); // 5000050000The loop needs no stack frames, so it works for any input size. IntelliJ IDEA has a Tail recursion inspection with a quick-fix called Replace tail recursion with iteration that performs this conversion.
5. Trampolines for Deep Recursion
A trampoline keeps the recursive style without growing the stack. Instead of calling itself, the method returns an object that describes the next call. A driver loop runs these objects one after another until one of them holds the final result.
The following example is a small TailCall interface, adapted from the approach in Venkat Subramaniam’s book Functional Programming in Java. The invoke() method uses Stream.iterate() as the driver loop.
@FunctionalInterface
interface TailCall<T> {
TailCall<T> next();
default boolean isDone() {
return false;
}
default T result() {
throw new UnsupportedOperationException("not done yet");
}
default T invoke() {
return Stream.iterate(this, TailCall::next)
.filter(TailCall::isDone)
.findFirst()
.orElseThrow()
.result();
}
}static <T> TailCall<T> done(T value) {
return new TailCall<>() {
public TailCall<T> next() {
throw new UnsupportedOperationException("already done");
}
public boolean isDone() {
return true;
}
public T result() {
return value;
}
};
}
static TailCall<Long> sumTrampoline(int n, long acc) {
return n == 0 ? done(acc) : () -> sumTrampoline(n - 1, acc + n);
}long million = sumTrampoline(1_000_000, 0).invoke(); // 500000500000The lambda () -> sumTrampoline(n – 1, acc + n) does not run the call, it only describes it. The trampoline handled one million levels that would overflow any default stack, at the cost of one small object per step, so a plain loop is still faster when we can write one.
6. Tail Recursion FAQs
Speed, Java versions and deep recursion come up in most tail recursion questions.
6.1. Is tail recursion faster than normal recursion in Java?
Not noticeably. Both versions make the same number of calls and keep the same number of frames, because Java does not optimize tail calls. The accumulator version can be faster when it changes the algorithm, such as Fibonacci going from O(2n) to O(n).
6.2. Does Java 21 or Java 25 support tail call optimization?
No. Virtual threads in Java 21 changed how threads use stacks, but they did not add tail-call elimination, and a deep tail-recursive method still throws StackOverflowError on Java 25.
6.3. Can every recursive method be made tail-recursive?
In theory yes, with continuation-passing style or an explicit stack, but in practice only linear recursion converts cleanly with an accumulator. For trees and graphs, the plain recursive version or an iterative version with a Deque is easier to read.
6.4. How do we avoid StackOverflowError with recursion in Java?
We convert the tail recursion into a loop, use a trampoline, or limit the depth by design, as binary search and balanced trees do. As a last resort, a thread created with a larger stack size, such as new Thread(null, task, “worker”, 64L << 20), allows deeper recursion. The recursion in Java guide shows the stack in detail.
7. Conclusion
A tail-recursive method makes its recursive call as the last action and carries its partial result in an accumulator. Languages such as Kotlin and Scala compile such methods into loops, but Java keeps one stack frame per call, so tail recursion alone does not prevent StackOverflowError.
In Java, the tail-recursive version is a step toward a plain while loop, because its parameters map one to one to loop variables. When the recursive style matters more than raw speed, a trampoline runs any depth in one stack frame.
8. References
- OpenJDK Project Loom wiki
- Kotlin docs, Tail recursive functions
- IntelliJ IDEA inspection, Tail recursion
- Venkat Subramaniam, Functional Programming in Java
Happy Learning !!
