Tail Recursion and Iteration in Java

End recursion means: the recursive call is the last action, and the result is passed through unchanged. Thus, the old frame is logically no longer needed.

Accumulator pattern:

long factTail(int n, long acc) {
  if (n <= 1) return acc;
  return factTail(n - 1, acc * n);
}

Equivalent iteration: a loop multiplies acc until n reaches 1.

Why this matters in Java: HotSpot does not automatically convert this into a loop. Deep tail recursion can still trigger a StackOverflowError. Therefore, in Java, for large depths, iterate or use an explicit Deque as a stack.

Where tail recursion is still important: passing to languages with TCO, reading functional specs, mechanical transformation of recursion → loop, and in contrast to divide-and-conquer recursion (Hanoi, Merge Sort), which combines after the call and is thus not tail-recursive.

Hanoi short form as a counterexample to tail recursion: two recursive calls plus a move in between, number of moves 2^n - 1.

Where used

Functional languages and non-JVM runtimes use tail call optimization to make tail recursion stack constant. On the HotSpot JVM, this is missing; however, tail recursion is still the right way of thinking before consciously translating it into a loop.

Depth

In a tail-recursive function, the recursive call is the last semantic action. The entire subsequent state can therefore be described by updated parameters. However, Java does not guarantee that such calls are executed without additional activation records.

A loop translates parameters into mutable state variables and keeps the memory requirement independent of the number of steps. This differs from divide-and-conquer approaches, where after a partial call, results still need to be combined or additional branches visited.

For deep tree or graph algorithms, a Deque can explicitly store open subproblems. This makes capacity, order, and error handling visibly controllable. The required memory does not disappear, but it is no longer managed implicitly by the call stack.

Difficulty levels

1. Distinguish the last recursive action from subsequent combination.
2. Transfer parameter state into a loop invariant.
3. Simulate recursive branches using an explicit Deque.

Pitfalls

A syntactically last line does not automatically mean tail-recursive if the result is further combined afterward. Such a form does not reliably protect in Java against excessive call depth either.