Java Performance Tuning

Recursion

Recursive algorithms are used because they’re often clearer and more elegant than the alternatives, and therefore have a lower maintenance cost than the equivalent iterative algorithm. However, recursion often (but not always) has a cost to it; recursive algorithms are frequently slower. So it is useful to understand the costs associated with recursion, and how to improve the performance of recursive algorithms when necessary.

Recursive code can be optimized by a clever compiler (as is done with some C compilers), but only if presented in the right way (typically, it needs to be tail-recursive: see Tail Recursion). For example, Jon Bentley^[49] found that a functionally identical recursive method was optimized by a C compiler if he did not use the ?: conditional operator (using if statements instead). However, it was not optimized if he did use the ?: conditional operator. He also found that recursion can be very expensive, taking up to 20 times longer for some operations that are naturally iterative. Bentley’s article also looks briefly at optimizing partial match searching in ternary search trees by transforming a tail recursion in the search into an iteration. See Chapter 11, for an example of tuning a ternary search tree, including an example of converting a recursive algorithm to an iterative one.

Tail Recursion

A tail-recursive function is a recursive function for which each recursive call to itself is a reduction of the original call. A reduction is the situation ...