# Recursive call vs while loop

**URL:** <https://discourse.julialang.org/t/recursive-call-vs-while-loop/7723>\
**Category:** Performance\
**Tags:** recursion\
**Created:** [December 12, 2017, 9:37pm UTC](https://discourse.julialang.org/t/recursive-call-vs-while-loop/7723 "2017-12-12T21:37:31Z")\
**Posts on this page:** 1\
**Showing post:** 18

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [October 31, 2018, 12:25pm UTC](https://discourse.julialang.org/t/recursive-call-vs-while-loop/7723/18 "2018-10-31T12:25:38Z")

</div>

> [@anon61610682](#):
>
> Is this something that could be fixed? Or, is this something I should remember — as a rule of thumb, should I simply prefer using loops to recursion?

Recursion can be a [powerful and elegant](https://en.wikipedia.org/wiki/Divide_and_conquer_algorithm) way to code. It can also sometimes lead to higher performance because of [improved cache locality](https://en.wikipedia.org/wiki/Cache-oblivious_algorithm), and can even sometimes lead to [more accurate algorithms](https://en.wikipedia.org/wiki/Pairwise_summation).

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](https://github.com/stevengj/18S096/blob/master/lectures/lecture4/memory-matrices.ipynb) or [transposition](https://github.com/stevengj/18S096/blob/master/lectures/other/Transposition.ipynb) (from my course notes) and [pairwise summation](https://github.com/JuliaLang/julia/pull/4039) in Julia `Base`.

This is also called [recursion coarsening](http://progforperf.github.io/Bentley_Rules.pdf), and my understanding is that it is [still a research problem](https://dl.acm.org/citation.cfm?id=663942) 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](https://github.com/JuliaLang/julia/issues/4964), in contrast to languages like Scheme where it is essential because tail calls are the primary iteration construct.

---

_[View the full topic](https://discourse.julialang.org/t/recursive-call-vs-while-loop/7723)._