# Recursion in Julia — bad idea?

**URL:** https://discourse.julialang.org/t/recursion-in-julia-bad-idea/99304
**Category:** Performance
**Tags:** recursion
**Created:** [May 23, 2023, 9:16pm UTC](https://discourse.julialang.org/t/recursion-in-julia-bad-idea/99304 "2023-05-23T21:16:58Z")
**Posts on this page:** 1
**Showing post:** 5

<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: [May 24, 2023, 12:35am UTC](https://discourse.julialang.org/t/recursion-in-julia-bad-idea/99304/5 "2023-05-24T00:35:38Z")

</div>

On the contrary, I think recursion is a great tool and use it often in Julia; of course, it has its limits, but no more so than in most other performance-oriented imperative languages (e.g. C).

For example, it is a great way to exploit memory locality in data structures, as I [demo’ed for matrix multiplication](https://discourse.julialang.org/t/julia-matrix-multiplication-performance/55175/12) for example (or for [FFTs](https://www.fftw.org/)). It can also be a nice way to express multidimensional algorithms, e.g. for [multidimensional Chebyshev interpolation](https://github.com/JuliaMath/FastChebInterp.jl/blob/d9330988e6f23f929e99c30eb597e69a6f67dd5e/src/eval.jl#L16-L56) or for [multidimensional in-place array reversal](https://github.com/JuliaLang/julia/pull/37367). Julia’s built-in `sum` function [uses recursion](https://github.com/JuliaLang/julia/blob/c470dc369865cf2f90ad34e25e110b72dd7fbd87/base/reduce.jl#L251-L275) to implement [pairwise summation](https://en.wikipedia.org/wiki/Pairwise_summation) for greater floating-point accuracy. And, of course, recursive sorting algorithms like [Quicksort](https://en.wikipedia.org/wiki/Quicksort) and [Merge sort](https://en.wikipedia.org/wiki/Merge_sort) are famous, and Julia’s `sort` function has both [recursive quicksort](https://github.com/JuliaLang/julia/blob/c470dc369865cf2f90ad34e25e110b72dd7fbd87/base/sort.jl#L2021-L2037) and [recursive mergesort](https://github.com/JuliaLang/julia/blob/c470dc369865cf2f90ad34e25e110b72dd7fbd87/base/sort.jl#L2039-L2081).

But you have to use recursion appropriately. If you are recursing thousands of times in an [imperative language](https://en.wikipedia.org/wiki/Imperative_programming), you should probably consider a loop (perhaps with an explicit stack/queue data structure). If each recursive call is extremely cheap, then you should consider “coarsening” your recursion (e.g. by enlarging the base case) to amortize the function-call overhead (this is true in any language, BTW, at least for non-tail calls). See also the discussion here: [Recursive call vs while loop - #18 by stevengj](https://discourse.julialang.org/t/recursive-call-vs-while-loop/7723/18)

> [@Oscar\_Smith](#):
>
> It’s not so much that Julia is the wrong tool, but that recursion in Julia is the wrong tool.

I think it’s a common myth that recursion is necessarily slow. The key trick that is usually missing from such discussions is to enlarge the base case.

---

_[View the full topic](https://discourse.julialang.org/t/recursion-in-julia-bad-idea/99304)._