# Type instability of nested recursive function
**URL:** https://discourse.julialang.org/t/type-instability-of-nested-recursive-function/78392
**Category:** Performance
**Tags:** type-stability
**Created:** [March 24, 2022, 1:53pm UTC](https://discourse.julialang.org/t/type-instability-of-nested-recursive-function/78392 "2022-03-24T13:53:58Z")
**Posts on this page:** 5
**Page:** 1
### Author:  [@ma-chengyuan](https://discourse.julialang.org/u/ma-chengyuan)
#### Post date: [March 24, 2022, 1:53pm UTC](https://discourse.julialang.org/t/type-instability-of-nested-recursive-function/78392/1 "2022-03-24T13:53:58Z")
I was writing some code where I need an inner function to be recursive, something like (highly simplified)
```julia
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`:
```julia
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
```julia
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)
---
### Author:  [@sbuercklin](https://discourse.julialang.org/u/sbuercklin)
#### Post date: [March 24, 2022, 2:53pm UTC](https://discourse.julialang.org/t/type-instability-of-nested-recursive-function/78392/2 "2022-03-24T14:53:49Z")
Is there a reason you need the closure over `x`? This looks like it would do the same thing, and is type-stable.
```julia
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
```
```julia
@code_warntype f1([1,2,3])
MethodInstance for f1(::Vector{Int64})
from f1(x::Vector{Int64}) in Main at REPL[22]:1
Arguments
#self#::Core.Const(f1)
x::Vector{Int64}
Body::Vector{Int64}
1 ─ Main.g!(x, 1, 1)
└── return x
```
```julia
@code_warntype g!([1,2,3],1,1)
MethodInstance for g!(::Vector{Int64}, ::Int64, ::Int64)
from g!(x, i, val) in Main at REPL[23]: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
```
---
### Author:  [@ma-chengyuan](https://discourse.julialang.org/u/ma-chengyuan)
#### Post date: [March 24, 2022, 3:24pm UTC](https://discourse.julialang.org/t/type-instability-of-nested-recursive-function/78392/3 "2022-03-24T15:24:08Z")
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.
---
### Author:  [@lawless-m](https://discourse.julialang.org/u/lawless-m)
#### Post date: [March 24, 2022, 3:29pm UTC](https://discourse.julialang.org/t/type-instability-of-nested-recursive-function/78392/4 "2022-03-24T15:29:43Z")
while it may look ugly perhaps `@inline g!(....` will make sure it adds no overhead
---
### Author:  [@anon56330260](https://discourse.julialang.org/u/anon56330260)
#### Post date: [March 28, 2022, 3:38am UTC](https://discourse.julialang.org/t/type-instability-of-nested-recursive-function/78392/5 "2022-03-28T03:38:10Z")
You can always use a NamedTuple to pack everything together and then unpack the value in inner function. A macro can automate this approach.