Recursive call vs while loop

Recursion can be a powerful and elegant way to code. It can also sometimes lead to higher performance because of improved cache locality, and can even sometimes lead to more accurate algorithms.

The one rule of thumb to keep in mind when coding recursion, in any language, is that if you care about performance you need to enlarge the base case to amortize the function-call overhead.

Some examples of this include cache-oblivious matrix multiplication or transposition (from my course notes) and pairwise summation in Julia Base.

This is also called recursion coarsening, and my understanding is that it is still a research problem for compilers to perform this kind of transformation automatically in any general language.

If you have a tail-recursive algorithm, on the other hand, recursion is usually uninteresting and has no particular advantages; you might as well rewrite it into the equivalent loop. That’s why there’s not much interest in implementing TCO for Julia, in contrast to languages like Scheme where it is essential because tail calls are the primary iteration construct.