# Any good resource to understand the issues with recursion in Julia?

I’m implementing basically the Median of Medians (actually, Median of Ninthers) algorithm for quick deterministic selection (see [original post]). It is recursive, as in the way to find a pivot is by calculating the median of ninthers of chunks of the array and that median is found by calling the `medianofninthers` of those ninthers.

I keep reading that Julia is not great with recursion and that TCO is not well supported, and that I should make the calls iterative instead of recursive, but then I see that Quick Sort implementation (which in essence is very similar to median of medians, but with a different pivot finding algorithm and of course without sorting) is recursive.

If I could gain some clarity on what the right approach is here, I’d really appreciate it!

For reference, this is the `medianofmedians!` function and the functions it calls (the recursion happens between `quickselect!` and `medianofmedianspartition!`, but I include `hoarepartition!` and `medianoffive!` for completeness, note that only hoarepartition uses inbounds macro because i’m still learning how and where to use).

(note: In the last post I was asked to add more code, please let me know if I’m going overboard here, I’m still figuring out the etiquette here.)

``````function medianofmedianspartition!(arr::AbstractVector)
len = length(arr)
if len < 5
sort!(arr)
return 1 + len ÷ 2
end
j = 1
i = 1
while i + 4 <= len
arr_view = @view(arr[i:(i+4)])
medianoffive!(arr_view)
arr[j], arr_view[3] = arr_view[3], arr[j]
i += 5
j += 1
end
j -= 1
quickselect!(@view(arr[1:j]), 1 + j ÷ 2, medianofmedianspartition!)
return hoarepartition!(arr, 1 + j ÷ 2)
end

function quickselect!(arr::AbstractVector, position::Integer, partitionfunc!::Function)
i = 1
j = length(arr)
if i == j
return
end
while true
new_position = i + partitionfunc!(@view(arr[i:j])) - 1
if new_position == position
return
elseif new_position > position
j = new_position - 1
else
i = new_position + 1
end
end
return
end

function hoarepartition!(arr::AbstractVector, pivot_index::Integer)
@inbounds pivot_value = arr[pivot_index]
@inbounds arr[pivot_index], arr[1] = arr[1], arr[pivot_index]
a = 2
b = length(arr)
@inbounds while a < b
while a <= b && arr[a] <= pivot_value
a += 1
end
while pivot_value < arr[b]
b -= 1
end
if a >= b
break
end
arr[a], arr[b] = arr[b], arr[a]
a += 1
b -= 1
end
@inbounds arr[a-1], arr[1] = arr[1], arr[a-1]
return a - 1
end

function medianoffive!(a::AbstractVector)
@assert length(a) == 5 "medianoffive! only works for arrays of 5 elements."
# We order x1 < x2 and x3 < x4
if a[1] > a[2]
a[1], a[2] = a[2], a[1]
end
if a[3] > a[4]
a[3], a[4] = a[4], a[3]
end
# We remove lowest of first 4 by comparing x1 and x3.
if a[1] < a[3]
a[1], a[5] = a[5], a[1]
if a[1] > a[2]
a[1], a[2] = a[2], a[1]
end
else
a[3], a[5] = a[5], a[3]
if a[3] > a[4]
a[3], a[4] = a[4], a[3]
end
end
# Now we have to find 2nd element out of x1 < x2, x3 < x4
if a[1] < a[3]
if a[2] < a[3]
a[2], a[3] = a[3], a[2]
return
else
return
end
else
if a[4] < a[1]
a[4], a[3] = a[3], a[4]
return
else
a[1], a[3] = a[3], a[1]
return
end
end
return
end
``````
1 Like

The issues with Julia & recursion are blown out of proportion. Julia recurses fine; it just doesn’t guarantee to optimize tail calls. There can be some problems with mutual recursion and type stability, but if your code is type stable and/or simple recursion, you shouldn’t have any issues.

11 Likes

Yes : recursion is fine with Julia !

I implemented optical rays simulation tool totally based on recursion with huge (>1000 ?) recursion depth with no issue and great performances:

``````function recursive_generate_rays_fluid!(reduce_ray!, state,celerity_domain, idx, time,
u::Point, pstart::Point, np::NumericalParameters, depth, power)
c₁,_,ρ₁ = cl_ct_rho(state)
u=normalize(u)
pend, pnext,uθ,state,next_state = advance_ds(pstart, u, np, state,celerity_domain)
c₂,_,ρ₂ = cl_ct_rho(next_state)

Δt = norm(pend - pstart) / c₁
time += Δt

reduce_ray!(pstart, pend, c₁, time, idx,power)

if depth <= np.maxdepth && time <= np.tmax  && power>np.power_threshold

uθr = maybeuθr(uθ, c₁, c₂) # refracted angle θr from incident angle θ
r,t = isnothing(uθr) ? (1.0,0.0) : rtpower_coeffs_fluid_fluid(uθr, uθ, c₁, c₂, ρ₁, ρ₂)
# reflection αf(α,θ,θ) =  π + α - θ - θᵣ
recursive_generate_rays_fluid!(reduce_ray!, state,celerity_domain, 2idx, time,
uαf(u,uθ,uθ), pend, np, depth+1, r*power)
# refraction α + θᵣ - θ
!isnothing(uθr) &&
recursive_generate_rays_fluid!(reduce_ray!, next_state,celerity_domain, 2idx+1, time,
uαr(u,uθ,uθr), pnext, np, depth+1, t*power)
end
end
``````
5 Likes

This is nonsense. Recursion is perfectly fine in Julia. See Recursion in Julia — bad idea? - #5 by stevengj

Julia doesn’t do TCO, but any algorithm where TCO is applicable is uninteresting for recursion in an imperative language — tail-call recursion is trivially written as a loop. Interesting applications of recursion tend to not be tail calls — for example, quicksort is not tail-recursive.

TCO has been discussed ad nauseam. See

11 Likes

Julia is no worse than most languages with recursion.
It doesn’t have tail call optimization, which means it doesn’t automatically rewrite recursive calls into loops.
Which means it is possible to blow out your stack if you recurse too deep. But that;s like really really deep. Like julia’s own inference algorithms often recurse over 400 times it is fine.

Most languages do not have tail call optimization.
And a lot of recursive patterns are not amenable to tail call optimization anyway.
Tail call optimization is mostly interesting for languages which do not have loops – so require you to write stuff recursively. This includes some functional langauges.
But not any imperative languages like julia.

4 Likes

(Clarification: TCO doesn’t rewrite all recursive calls into loops, only tail calls. This is an extremely small minority of recursive algorithms in practice, and does not include any interesting recursive algorithms. TCO is basically only important for functional languages like Scheme in which recursion is preferred to loops.)

8 Likes

Thanks for all the links! I had read your post already actually, but there’s also as you mentioned several posts and notes recommending against it or asking about it. I get that recursion can be an issue with any imperative languages if the stack grows too much, but what I wasn’t grasping was whether there was something special about how Julia’s compiler handles it.

Sorry for adding to the noise on the topic, but if it happens so often, maybe it means that it warrants a clarification note in the official docs? I’d be happy to draft it if someone with your expertise (or other experts) are willing to revise . Or maybe it’s done and I haven’t found it.

1 Like

Yes, which I said later in same message.

Yes, maybe a section on recursion in the performance tips?

4 Likes

Perfect I’ll get to it and submit a PR!

1 Like

Any language can blow up the stack with too many recursive calls, whether or not it does tail call optimization because the nontrivial recursions are not simple tail calls. Functional languages don’t have a magically efficient stack, they just need TCO because they don’t have loop structures.

4 Likes

Right that makes sense, I don’t know enough about functional programming to know how it is compiled but it stands to reason.