# Best data structure for recursive functions?

**URL:** <https://discourse.julialang.org/t/best-data-structure-for-recursive-functions/112289>\
**Category:** New to Julia\
**Tags:** question\
**Created:** [March 29, 2024, 1:12pm UTC](https://discourse.julialang.org/t/best-data-structure-for-recursive-functions/112289 "2024-03-29T13:12:44Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![phantom](https://avatars.discourse-cdn.com/v4/letter/p/e0b2c6/32.png) [@phantom](https://discourse.julialang.org/u/phantom)\
**Post date:** [March 29, 2024, 1:12pm UTC](https://discourse.julialang.org/t/best-data-structure-for-recursive-functions/112289/1 "2024-03-29T13:12:45Z")

</div>

Hi Hope everyone is having a good friday.

Suppose a function tests for an initial condition prior to running an inner function on elements of a series of datasets. If the initial condition fails, the function skips to the next dataset. After iterating through all the datasets it repeats the process on all the incomplete datasets.

A crude example might be.

```julia
using Threads 

g1 = [1,2,3]
g2 = [4,5,6]
testpop = [g1,g2] 

function main(testpop, cont = Ref(true))
  untested = []
  for group in testpop
        condition = second(now())/10    
        @spawn for people in group
              cont [] || break
              if condition <= rand(1:12) 
                 push!(untested, group) 
                 break 
              else   
                 fun1(people)
                 popfirst!(group)
              end
        end
        return(cont)
   end 
   !isempty(untested) && main(untested)  
end  

```

2 quick questions.

1. Given stvenjg’s [post](https://discourse.julialang.org/t/recursive-call-vs-while-loop/7723/23) about tail recursive algorithms not having much advantages in julia, should a different approach be employed as `testpop` and `gn` get larger? Is it helpful/possible to [enlarge the base case](https://discourse.julialang.org/t/recursion-in-julia-bad-idea/99304/2) here?

2. Assuming recursion is used, would it be helpful to use different data structures like channels instead of arrays?

Sorry for the basic questions. Just want to make sure i’m going about this correctly in julia. Thanks!

---

<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:** [March 29, 2024, 2:14pm UTC](https://discourse.julialang.org/t/best-data-structure-for-recursive-functions/112289/2 "2024-03-29T14:14:17Z")

</div>

Your tail recursion here can be trivially replaced by a `while` loop (like all self tail recursion). Do that.

You are also using untyped containers (the `Any` array `[]`).

Parallel mutation of an array like this isn’t thread safe. You need a lock or a different data structure to avoid a race condition.

---

<div class="post-metadata">

**Author:** ![phantom](https://avatars.discourse-cdn.com/v4/letter/p/e0b2c6/32.png) [@phantom](https://discourse.julialang.org/u/phantom)\
**Post date:** [March 29, 2024, 10:15pm UTC](https://discourse.julialang.org/t/best-data-structure-for-recursive-functions/112289/3 "2024-03-29T22:15:10Z")

</div>

Wow thanks so much for this and your other posts on recursion.

Originally I used `@async` and `Ref` to break the loop with an external command. However the [warning](https://docs.julialang.org/en/v1/base/parallel/#Base.@async) in the docs encouraged the use of @spawn over @async. Am I correct in understanding that in cases involving the parallel mutation of arrays `@async` is still preferable over `@spawn` becuase it disables the migration of the _parent_ task across worker threads?

With a while loop it seems like breaking the loop with an external command becomes more periphrastic than using tail end recursion. Something like

```julia
function main(testpop, cont = Ref(true))
    @async while all(!isempty,testpop) && cont[] 
        for group in testpop
            condition = second(now())/10    
            @async for people in group
                cont [] || break      
                if condition <= rand(1:12)  
                    break 
                else   
                    fun1(people)
                    popfirst!(group)
                end
            end
            return(cont)
        end 
    end
    return(cont) 
end 

```

When you mention in this [post](https://discourse.julialang.org/t/recursive-call-vs-while-loop/7723/18) that

> [@Recursive call vs while loop](https://discourse.julialang.org/t/recursive-call-vs-while-loop/7723/18):
>
> 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.

Did you mean that there are meaningful disadvantages to tail end recursion in julia? Or is it just bad practice in general?

---

<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:** [March 29, 2024, 10:26pm UTC](https://discourse.julialang.org/t/best-data-structure-for-recursive-functions/112289/4 "2024-03-29T22:26:45Z")

</div>

> [@phantom](#):
>
> Am I correct in understanding that in cases involving the parallel mutation of arrays `@async` is still preferable over `@spawn`

No `@async` is used for [asynchronous tasks](https://docs.julialang.org/en/v1/manual/asynchronous-programming/) that aren’t necessarily parallel at all. If you are running everything on a single thread (and just switching back and forth between tasks) then race conditions are less of an issue (since you have more control over when task switches occur), but that’s not helpful if you actually want your tasks running on parallel hardware threads.

> [@phantom](#):
>
> Did you mean there meaningful disadvantages to tail end recursion in julia? Is it just bad practice in general?

Yes, tail recursion pushes a new stack frame while a loop does not. Because self tail recursion is (by definition) trivially rewritable as a loop, there’s basically no reason to use it compared to a loop in Julia.

(As opposed to non-tail recursion, which can be quite handy as I explained in the thread you linked.)

---

<div class="post-metadata">

**Author:** ![Dan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dan/32/42581_2.png) [@Dan](https://discourse.julialang.org/u/Dan)\
**Post date:** [March 29, 2024, 11:01pm UTC](https://discourse.julialang.org/t/best-data-structure-for-recursive-functions/112289/5 "2024-03-29T23:01:33Z")

</div>

> [@phantom](#):
>
> `main(testpop, continue = Ref(true))`

It’s better not to use `continue` as a parameter name since it is a Julia keyword used as part of the `for` loop construct:

```julia
for .... in ...
    break
    continue
end

```

(use `?continue` in the REPL for details)

---

<div class="post-metadata">

**Author:** ![phantom](https://avatars.discourse-cdn.com/v4/letter/p/e0b2c6/32.png) [@phantom](https://discourse.julialang.org/u/phantom)\
**Post date:** [March 29, 2024, 11:20pm UTC](https://discourse.julialang.org/t/best-data-structure-for-recursive-functions/112289/6 "2024-03-29T23:20:23Z")

</div>

Thanks so much, that clarifies things a lot. I’m still confused about this note about thread safety where you mention

> [@stevengj](#):
>
> Parallel mutation of an array like this isn’t thread safe. You need a lock or a different data structure to avoid a race condition.

Presumably a data structure like Channels would alleviate that problem? Are there other data structures that could be appropriate here?

Also you mention

> [@stevengj](#):
>
> No `@async` is used for [asynchronous tasks](https://docs.julialang.org/en/v1/manual/asynchronous-programming/) that aren’t necessarily parallel at all.

However the [warning](https://docs.julialang.org/en/v1/base/parallel/#Base.@async) in the docs reads

> It is strongly encouraged to favor `Threads.@spawn` over `@async` always **even when no parallelism is required** especially in publicly distributed libraries. This is because a use of `@async` disables the migration of the _parent_ task across worker threads in the current implementation of Julia.

Are arrays the exception to this warning? Should a caveat be that in cases where thread safety is a bigger concern than parallelism i.e. the present use of arrays, `@async` is actually preferred because it might serve as the “lock” you mentioned above?

---

<div class="post-metadata">

**Author:** ![phantom](https://avatars.discourse-cdn.com/v4/letter/p/e0b2c6/32.png) [@phantom](https://discourse.julialang.org/u/phantom)\
**Post date:** [March 29, 2024, 11:26pm UTC](https://discourse.julialang.org/t/best-data-structure-for-recursive-functions/112289/7 "2024-03-29T23:26:51Z")

</div>

Thanks so much for pointing that out! I edited it to `cont` so it doesn’t mislead me or other students in the future…or distort some LLM.