# Tail recursion is functionally equivalent to iteration

Description:

Since Java does not yet support tail call optimization, describe how to transform a simple tail recursive function into a loop and why one is typically preferred over the other.

Solution:

Here is an example of a typical recursive function, computing the arithmetic series 1, 2, 3…N. Notice how the addition is performed after the function call. For each recursive step, we add another frame to the stack.

``````public int sumFromOneToN(int n) {
if (n < 1) {
return 0;
}

return n + sumFromOneToN(n - 1);
}
``````

Tail recursion occurs when the recursive call is in the tail position within its enclosing context - after the function calls itself, it performs no additional work. That is, once the base case is complete, the solution is apparent. For example:

``````public int sumFromOneToN(int n, int a) {
if (n < 1) {
return a;
}

return sumFromOneToN(n - 1, a + n);
}
``````

Here you can see that `a` plays the role of the accumulator - instead of computing the sum on the way down the stack, we compute it on the way up, effectively making the return trip unnecessary, since it stores no additional state and performs no further computation. Once we hit the base case, the work is done - below is that same function, “unrolled”.

``````public int sumFromOneToN(int n) {
int a = 0;

while(n > 0) {
a += n--;
}

return a;
}
``````

Many functional languages natively support tail call optimization, however the JVM does not. In order to implement recursive functions in Java, we need to be aware of this limitation to avoid `StackOverflowError`s. In Java, iteration is almost universally preferred to recursion.

Author

Credit: 3870

Nothing
Author's Other questions
 What are Reflections? What does the following code usually output? And why usually? Where would you use LinkedList and where an ArrayList? Identify the Autoboxing and the Unboxing in the following example: What is Auto-boxing and Unboxing, and does it impact performance? Primitive vs Object types? What is the parent class that every other class extends from? Why is Java said to be 'write once, run everywhere'? What are static methods and fields? What is JPA and how is it different from JDBC? What is the difference between an Application server and servlet container? Given the following example code, which overrides are valid and which one aren't (with explanation)? What types of Exceptions exist in Java (and what is the difference)? Name few common Exceptions of each type. What are default methods? Why are exceptions expensive in Java? What is the problem with the following example and does it compile? What are generics in Java? What's the difference between a HashSet and a LinkedHashSet? What's the synchronized version of a HashMap? What's the difference between StringBuilder and StringBuffer?