# Type instability of nested recursive function

I was writing some code where I need an inner function to be recursive, something like (highly simplified)

``````function f1(x::Vector{Int64})
function g(i, val)
i <= length(x) || return
g(i + 1, val)
x[i] = val
end
g(1, 1)
x
end
``````

And when I ran it with `@code_warntype` I was surprised to see a `Core.Box`:

``````Arguments
#self#::Core.Const(f1)
x::Vector{Int64}
Locals
g@_3::Core.Box
g@_4::Union{}
g@_5::Union{}
Body::Vector{Int64}
1 ─       (g@_3 = Core.Box())
│   %2  = Main.:(var"#g#17")::Core.Const(var"#g#17")
│   %3  = Core.typeof(x)::Core.Const(Vector{Int64})
│   %4  = Core.apply_type(%2, %3)::Core.Const(var"#g#17"{Vector{Int64}})
│   %5  = %new(%4, x, g@_3)::var"#g#17"{Vector{Int64}}
│         Core.setfield!(g@_3, :contents, %5)
│   %7  = Core.isdefined(g@_3, :contents)::Bool
└──       goto #3 if not %7
2 ─       goto #4
3 ─       Core.NewvarNode(:(g@_5))
└──       g@_5
4 ┄ %12 = Core.getfield(g@_3, :contents)::Any
│         (%12)(1, 1)
└──       return x
``````

From the message it appears that the type instability is caused by `g` trying to capture `g` itself in its defining environment. This causes a self-referential type to be created and confuses the compiler.

My temporary solution is to use

``````function f2(x::Vector{Int64})
function h(i, val, self)
i <= length(x) || return
self(i + 1, val, self)
x[i] = val
end
h(1, 1, h)
x
end
``````

then `h` would not need to capture itself. This does prevents some memory allocations, but I am unsure if this is the fastest way.

Is there a better way to work around this issue? (while keeping the recursion. In the actual code it is very difficult to convert the recursion into a loop)

Is there a reason you need the closure over `x`? This looks like it would do the same thing, and is type-stable.

``````function f1(x::Vector{Int64})
g!(x, 1, 1)
return x
end

function g!(x, i, val)
if i > length(x)
g!(x, i + 1, val)
x[i] = val
end
return nothing
end
``````
``````@code_warntype f1([1,2,3])
MethodInstance for f1(::Vector{Int64})
from f1(x::Vector{Int64}) in Main at REPL:1
Arguments
#self#::Core.Const(f1)
x::Vector{Int64}
Body::Vector{Int64}
1 ─     Main.g!(x, 1, 1)
└──     return x
``````
``````@code_warntype g!([1,2,3],1,1)
MethodInstance for g!(::Vector{Int64}, ::Int64, ::Int64)
from g!(x, i, val) in Main at REPL:1
Arguments
#self#::Core.Const(g!)
x::Vector{Int64}
i::Int64
val::Int64
Body::Nothing
1 ─ %1 = Main.length(x)::Int64
│   %2 = (i > %1)::Bool
└──      goto #3 if not %2
2 ─ %4 = (i + 1)::Int64
│        Main.g!(x, %4, val)
└──      Base.setindex!(x, val, i)
3 ┄      return Main.nothing
``````
1 Like

Thanks! This approach does work, but the actual `g` in my code uses 5 bindings from the outer function, so moving the inner function outsides would add a lot of arguments.

while it may look ugly perhaps `@inline g!(....` will make sure it adds no overhead

You can always use a NamedTuple to pack everything together and then unpack the value in inner function. A macro can automate this approach.

1 Like