# How to handle unknown length returns in recursion without allocating

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?

1 Like

Would something like

``````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

``````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

``````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

``````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}})
``````

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

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. 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.)

3 Likes