Tail recursion makes the recursive call the method’s final operation. This form can be optimized into iteration, but Java does not guarantee that optimization, so sufficiently deep calls may still cause StackOverflowError. section 5.4.1 section 5.5
Accumulate before the recursive call
A summation function can carry the partial result in an accumulator. When the limit reaches zero, it returns the accumulator; otherwise, it decreases the limit and makes the recursive call with the updated result. Kotlin’s tailrec modifier can turn this pattern into a loop in JVM bytecode, allowing large inputs such as 1,000,000. section 5.4.1
tailrec fun sum(limit: Long, accumulator: Long = 0): Long {
if (limit == 0L) return accumulator
return sum(limit - 1, accumulator + limit)
}
Shows the accumulator-based Kotlin pattern whose recursive call is the final operation. section 5.4.1
Use these distinctions when applying or reviewing tail recursion:
- Treat the recursive call as tail-recursive only when no operation remains afterward; accumulating the result before the call preserves that property. section 5.4.1
- Do not assume Java will optimize tail recursion: some virtual machines may do so during JIT compilation, but the behavior is not guaranteed. section 5.4.1
- Rewrite tail recursion as a loop when stack depth matters; IntelliJ IDEA offers Replace Tail Recursion With Iteration. section 5.4.1 section 5.5
- Use heap-based structures such as ArrayDeque for non-tail recursive traversals, and track visited elements when cycles are possible. section 5.5
/**
* @param s string to search in
* @param start start offset
* @param c symbol to search
* @return position of symbol c inside string s
* starting from start offset; -1 if not found
*/
static int indexOf(String s, int start, char c) {
if (start >= s.length()) return -1;
if (s.charAt(start) == c) return start;
return indexOf(s, start + 1, c);
}
Provides a tail-recursive string index search whose call is the final operation. section 5.4.1
static int indexOf(String s, int start, char c) {
while (true) {
if (start >= s.length()) return -1;
if (s.charAt(start) == c) return start;
start = start + 1;
}
}
Shows the equivalent iterative index search, avoiding possible stack overflow. section 5.4.1
