# Emulating recursive types, apparently without drawbacks

**URL:** <https://discourse.julialang.org/t/emulating-recursive-types-apparently-without-drawbacks/139796>\
**Category:** General Usage\
**Tags:** performance, type, recursion\
**Created:** [October 2, 2026, 6:59pm UTC](https://discourse.julialang.org/t/emulating-recursive-types-apparently-without-drawbacks/139796 "2026-10-02T18:59:57Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![skraemer](https://avatars.discourse-cdn.com/v4/letter/s/4bbf92/32.png) [@skraemer](https://discourse.julialang.org/u/skraemer)\
**Post date:** [October 2, 2026, 6:59pm UTC](https://discourse.julialang.org/t/emulating-recursive-types-apparently-without-drawbacks/139796/1 "2026-10-02T18:59:57Z")

</div>

I was lately having a lot of trouble with recursive types, and eventually even triggered compiler bugs. Even worse, having a recursive type appear just once in field-of-…-field-types requires to carry it through much more complicated parametric versions of such.

It seems to me that you can always work around this though and achieve essentially equivalent functionality, with no relevant cost. Though I am interested in what I have missed. I have not been able to find the construction below, and will be glad to be pointed to contributions that have done the same.

If you want to skip the reasoning, just have a look at the last, longer code. It basically boils down to stricly necessary boxing at some point in the chain to a field-of-…-field-type using the recursive type:

**Recursive types require boxing at some level:**  
First, trying to create a simple, recursive isbits types will fail (and a union fieldtype won`t do it either)

```julia
struct Test
    t::Test
    Test() = new() 
    Test(t::Test) = new(t)
end
sizeof(Test) # 8
isbitstype(Test) # false

```

What is more interesting is that an incomplete constructor in a fieldtype can change how the _top type_ handles that field. This is due to the way Julia indicates and forwards `undef`.

As you can see below, the top type `Wrapper{T2}` of size `8` boxes its field for the sole reason that the subtype `T2` (of size `16`) contains an incomplete constructor:

```julia
struct Complete{S}
    s::S
    SubInc(s::S) where S = new{S}(s)
end

struct Incomplete{S}
    s::S
    SubInc() = new{S}() # equals Complete but for this constructor
    SubInc(s::S) where S = new{S}(s)
end

struct Wrapper{T}
    x::T
    Incomplete(x::T) where T = new{T}(x)
end

T1 = Incomplete{Bool} # 1 (the "incomplete" constructor will just overtake random bits)
sizeof(T1) # 1
sizeof(Wrapper{T1}) # 1

VecVec = Tuple{Vector{Bool},Vector{Bool}}
sizeof(VecVec) # 16

T2 = Incomplete{VecVec} 
sizeof(T2) # 16
sizeof(Wrapper{T2}) # 8 (! boxes)

T3 = Complete{VecVec} 
sizeof(T3) # 16
sizeof(Wrapper{T3}) # 16 (does not box)

T4 = Union{Bool,VecVec}
sizeof(Wrapper{T4}) # 8 (! union fieldtype causes boxing as well)

```

**Abstract fieldtypes where there must be a box:**  
These boxing barriers change how to look at recursive types. Essentially, at some point down into a field-of-…-field-type, the behaviour in regard of boxing is essentially as of a field of mutable type. Within `Wrapper{T2}`, the type `Incomplete{VecVec}` may for instance as well be replaced with a mutable version of it with const fields. But for that matter, one could then replace `Incomplete{T2}` just with the unionall type `Incomplete` or some abstract suptype altogether.

**Implicitly ensuring type stability:**  
The remaining problem with type instability of getting that now type instable field can somewhat easily be fixed a posterior by telling `getproperty` what that fieldtype is _intended_ to be, and `setproperty!` for a mutable type as well as any other point `getfield` or `setfield!` is used.

There is some marginal effort for Julia to check the type via `::Vector{_v_type(as)}`, but at the same time, the emulated recursive type `S` seemingly performs marginally better at other tasks compared to the true recursive type `RS`.

The tests are also intended to simulate warmer and colder caches, so they cycle through vectors of different size:

```julia
if !@isdefined(AS)
    abstract type AS end

    struct SR <: AS
        v::Vector{SR} # self-referential
        SR(ell::Int) = SR(Vector{SR}(undef, ell))
        SR(v::Vector{SR}) = new(v)
    end

    struct S <: AS
        v::Vector{T} where T<:AS # implicitly set through _v_type
        S(ell::Int) = S(Vector{S}(undef, ell))
        S(v::Vector{S}) = new(v)
    end
end
# here one sets the intended type:
_v_type(::T) where T<:AS = T

# ensure concrete return type for S (and set an artifial property call (for testing purposes)
Base.getproperty(as::AS, sym::Symbol) = sym === :ell ? length(as.v) : getfield(as, :v)::Vector{_v_type(as)}

## the rest is for testing (and avoiding infinite text output)
Base.show(io::IO, as::AS) where IO = show(io, typeof(as))
Base.display(as::AS) = show(typeof(as))
Base.display(v::Vector{<:AS}) = display(typeof(v))
Base.print(io::IO, as::AS) where IO = show(io, typeof(as))
# function that requires one getproperty(as, :v) and one getproperty(as, :ell)
foo(as::AS) = sum(x->x.ell, as.v)

function make_collection(n::Int, ::Type{T}) where T<:AS
    collection = [T(n) for _ = 1:n]
    for e = collection
        for j = eachindex(e.v)
            e.v[j] = collection[j]
        end
    end
    return collection
end

function time(n::Int, ::Type{T}) where T<:AS
    t1 = (@timed collection = make_collection(n, T)).time

    t2 = (@timed for s = collection
        for i = 1:n
            s.v[i] = collection[i]
        end
    end).time

    a = 0
    t3 = (@timed for s = collection
        a += foo(s)
    end).time

    return (a, t1, t2, t3)
end

function timeall(n)
    println("n = $n:")
    GC.gc()
    GC.gc()
    (a_sr, tsr1, tsr2, tsr3) = (0, 0.0, 0.0, 0.0)
    (a_s, ts1, ts2, ts3) = (0, 0.0, 0.0, 0.0)
    for _ = 1:Int(round(1e8/n^2))
        (a_sr, tsr1, tsr2, tsr3) = (a_sr, tsr1, tsr2, tsr3) .+ time(n, SR)
    end
    GC.gc()
    GC.gc()
    for _ = 1:Int(round(1e8/n^2))
        (a_s, ts1, ts2, ts3) = (a_s, ts1, ts2, ts3) .+ time(n, S)
    end
    r3 = x->round(x, sigdigits=3)
    println("SR: $(r3(tsr1)) $(r3(tsr2)) $(r3(tsr3))")
    println("S: $(r3(ts1)) $(r3(ts2)) $(r3(ts3))")
    println("ratio S / SR: $(r3(ts1/tsr1)) $(r3(ts2/tsr2)) $(r3(ts3/tsr3))")
    println()
end

timeall(5)
timeall(10)
timeall(100)
timeall(1000)
# n = 5:
# SR: 0.716 0.182 0.145
# S: 0.662 0.174 0.145
# ratio S / SR: 0.925 0.959 1.0

# n = 10:
# SR: 0.347 0.102 0.0839
# S: 0.322 0.114 0.0744
# ratio S / SR: 0.929 1.12 0.886

# n = 100:
# SR: 0.159 0.0763 0.0506
# S: 0.182 0.0865 0.053
# ratio S / SR: 1.14 1.13 1.05

# n = 1000:
# SR: 0.435 0.0717 0.0715
# S: 0.454 0.0748 0.0679
# ratio S / SR: 1.04 1.04 0.95

```

**General scheme as pseudocode:**  
Looking at this more generally, one can always do so at the one point boxing would occur or where one purposely sets the mutable type. So, for instance, when the type `C` has an incomplete constructur, or is mutable, one could change

```julia
struct RecType; field::A{B{C{D{RecType}}}}; end

```

to

```julia
abstract type AC{T} end
struct C{T} <: AC{T}; (...); end
struct RecType; field::A{B{AC{D{RecType}}}}; end

function Base.getproperty(b::B{AC{T}}, sym::Symbol) where T 
if sym === :fc_for_C
   getfield(b, sym)::C{T}
else 
   getfield(b, sym) # or some further checks
end
# and ensuring at other points where getfield is called

```