# How to handle unknown length returns in recursion without allocating

**URL:** <https://discourse.julialang.org/t/how-to-handle-unknown-length-returns-in-recursion-without-allocating/88909>\
**Category:** General Usage\
**Tags:** question\
**Created:** [October 18, 2022, 12:19pm UTC](https://discourse.julialang.org/t/how-to-handle-unknown-length-returns-in-recursion-without-allocating/88909 "2022-10-18T12:19:01Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![jacobusmmsmit](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jacobusmmsmit/32/217669_2.png) [@jacobusmmsmit](https://discourse.julialang.org/u/jacobusmmsmit)\
**Post date:** [October 18, 2022, 12:19pm UTC](https://discourse.julialang.org/t/how-to-handle-unknown-length-returns-in-recursion-without-allocating/88909/1 "2022-10-18T12:19:01Z")

</div>

I have a recursive function `f(x, data)` which can return anywhere between 1 and `length(x)` elements. All I want to be able to do is iterate over the return value of `f` so the result doesn’t need to be instantiated into a `Tuple`, for example, but I can’t figure out how to return an iterator over the result, or whether I even need to worry about it.

My reason for asking is that I could simply have the returns be wrapped in `Tuple`, but the length of a `Tuple` is part of its type, and so the function would not be stable. I’m looking to not allocate a vector, and not have type instability. How can I do this?

---

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [October 18, 2022, 1:19pm UTC](https://discourse.julialang.org/t/how-to-handle-unknown-length-returns-in-recursion-without-allocating/88909/2 "2022-10-18T13:19:46Z")

</div>

Would something like

```julia
f(xs) = (x for x in xs)

@show typeof(f([1, 2, 3]))
for x in f([1, 2, 3])
    @show x
end
@show length(f([1, 2, 3]))

```

resulting in

```julia
typeof(f([1, 2, 3])) = Base.Generator{Vector{Int64}, typeof(identity)}
x = 1
x = 2
x = 3
length(f([1, 2, 3])) = 3

```

qualify? But there are caveats, for example

```julia
f(xs) = (x for x in xs if x != 1)

@show typeof(f([1, 2, 3]))
for x in f([1, 2, 3])
    @show x
end
@show length(f([1, 2, 3]))

```

yielding

```julia
typeof(f([1, 2, 3])) = Base.Generator{Base.Iterators.Filter{var"#7#8", Vector{Int64}}, typeof(identity)}
x = 2
x = 3
ERROR: MethodError: no method matching length(::Base.Iterators.Filter{var"#7#8", Vector{Int64}})

```

---

<div class="post-metadata">

**Author:** ![jacobusmmsmit](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jacobusmmsmit/32/217669_2.png) [@jacobusmmsmit](https://discourse.julialang.org/u/jacobusmmsmit)\
**Post date:** [October 18, 2022, 1:38pm UTC](https://discourse.julialang.org/t/how-to-handle-unknown-length-returns-in-recursion-without-allocating/88909/3 "2022-10-18T13:38:28Z")

</div>

Yeah you found my problem, in a way. The iterator needs a compile-time length which I guess isn’t possible.

---

<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 18, 2022, 1:45pm UTC](https://discourse.julialang.org/t/how-to-handle-unknown-length-returns-in-recursion-without-allocating/88909/4 "2022-10-18T13:45:35Z")

</div>

The general allocation-free way to do this is to define your own type `struct FooIterator` with an `iterate` method. For example, see the [`combinations` function in Combinatorics.jl](https://github.com/JuliaMath/Combinatorics.jl/blob/d1b633bffd1ed7ff3301e38f71cf37f415f19d1d/src/combinations.jl). This may require a bit of rethinking of how your function works, since it needs to be rearranged to compute return values one at a time as `iterate` is called.

Otherwise you should just return an array if you want a dynamically sized container, not a tuple. (No need to optimize allocations unless they are performance-critical, and type instability is generally worse than array allocations.)