# Type-stability of recursive functions

**URL:** <https://discourse.julialang.org/t/type-stability-of-recursive-functions/78946>\
**Category:** General Usage\
**Tags:** type-stability, recursion\
**Created:** [April 3, 2022, 2:47pm UTC](https://discourse.julialang.org/t/type-stability-of-recursive-functions/78946 "2022-04-03T14:47:43Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![nchisholm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nchisholm/32/37414_2.png) [@nchisholm](https://discourse.julialang.org/u/nchisholm)\
**Post date:** [April 3, 2022, 2:47pm UTC](https://discourse.julialang.org/t/type-stability-of-recursive-functions/78946/1 "2022-04-03T14:47:43Z")

</div>

I have challenged myself to write a (ideally type-stable) function that computes the determinant of (small) matricies using the O(n!) recursive expansion formula without resorting to `@generated`. I ended up with the following.

```julia
# Compute determinant of a matrix with equal-length row/column vectors `vs`
det(vs::Vararg{Any,N}) where N = _det(ntuple(identity, N), vs)

@inline _det((ind,)::NTuple{1,Int}, (v,)::NTuple{1,Any}) = getindex(v, ind)

@inline _det(inds::NTuple{N,Int}, (v, vs...)::NTuple{N,Any}) where N =
    +(map((sgn, (i, is...)) -> flipsign(v[i], sgn) * _det(is, vs),
          NTuple{N,Int}(altsigns(Int)), swapeach_1st(inds))...)

```

which seems to give the correct numerical result.

The helper functions used in `_det` are below.

```julia
using Static
const CanonicalInt = Union{StaticInt, Int}

# Like `ntuple`, but uses `StaticInt`s
sntuple(f, n::StaticInt) = _sntuple(f, n, n)
_sntuple(_, ::StaticInt, ::StaticInt{0}) = ()
_sntuple(f, n::StaticInt, i::StaticInt) =
    (f(n - i + static(1)), _sntuple(f, n, i - static(1))...)

altsigns(init) = Iterators.cycle((init, -init))
altsigns(T::Type) = altsigns(oneunit(T))
# altsigns(Int) -> (1, -1, 1, -1, ...)

# Return the input tuple with the element at the index `i` swapped with the
# first element.
# julia> swap_1st(static(2), ('a', 'b', 'c'))
# ('b', 'a', 'c')
function swap_1st(i::StaticInt, tup::Tuple)
    N = Arr.static_length(tup)
    1 ≤ i ≤ N || return tup
    (tup[i], sntuple(j -> tup[j], i - static(1))...,
             sntuple(j -> tup[j+i], N - i)...)
end

# Return a tuple of tuples where the ith tuple swaps the 1st and i-th elements
# of the input tuple.
# julia> swapeach_1st(('a', 'b', 'c'))
# (('a', 'b', 'c'), ('b', 'a', 'c'), ('c', 'a', 'b'))
swapeach_1st(tup::NTuple{N,Any}) where {N} =
    sntuple(i -> swap_1st(i, tup), static(N))

```

The function `sntuple` is necessary to make `swapeach_1st` type-stable and uses the `Static` package.

My goal with this is for `det` to `@inline` roughly as follows, generating an explicit formula for an n \times n determinant at compile time without need for `@generated`.

```julia
det(v1, v2, v3)

_det((1,2,3), (v1, v2, v3))

(+v1[1]) * _det((2,3), (v2, v3)) +
    (-v1[2]) * _det((1,3), (v2, v3)) +
    (+v1[3]) * _det((1,2), (v2, v3))

v1[1] * ((+v2[2]) * _det((3,), (v3,)) + (-v2[3]) * _det((2,), (v3,))) -
    v1[2] * ((+v2[1]) * _det((3,), (v3,)) + (-v2[3]) * _det((1,), (v3,))) +
    v1[3] * ((+v2[1]) * _det((2,), (v3,)) + (-v2[2]) * _det((1,), (v3,)))

v1[1] * (v2[2] * v3[3] - v2[3] * v3[2]) -
    v1[2] * (v2[1] * v3[3] - v2[3] * v3[1]) +
    v1[3] * (v2[1] * v3[2] - v2[2] * v3[1])

```

Interestingly, `det` is type-stable for 2 \times 2 and 3 \times 3 matrices, but not 4 \times 4 matrices.

```julia
det(eachcol(rand(3,3))...) # type stable -> Float64
det(eachcol(rand(4,4))...) # not type stable -> Any

```

Can anyone offer more info on what is happening? Is it possible to restore type stability to the `4x4` case? (It wouldn’t be very practical to use this function on much larger matrices anyway.)

Here is the output of `@code_warntype` on `_det` for the 3x3 case

```julia
julia> @code_warntype _det((1,2,3), NTuple{3}(eachcol(mat3x3)))

MethodInstance for _det(::Tuple{Int64, Int64, Int64}, ::Tuple{SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}})
  from _det(inds::Tuple{Vararg{Int64, N}}, ::Tuple{Vararg{Any, N}}) where N in Main at In[11]:7
Static Parameters
  N = 3
Arguments
  #self#::Core.Const(_det)
  inds::Tuple{Int64, Int64, Int64}
  @_3::Tuple{SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}}
Locals
  #25::var"#25#26"{SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, Tuple{SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}}}
  @_5::Int64
  v::SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}
  vs::Tuple{SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}}
Body::Float64
1 ─ nothing
│ %2 = Base.indexed_iterate(@_3, 1)::Core.PartialStruct(Tuple{SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, Int64}, Any[SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, Core.Const(2)])
│ (v = Core.getfield(%2, 1))
│ (@_5 = Core.getfield(%2, 2))
│ (vs = Base.rest(@_3, @_5::Core.Const(2)))
│ %6 = Main.:(var"#25#26")::Core.Const(var"#25#26")
│ %7 = Core.typeof(v)::Core.Const(SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true})
│ %8 = Core.typeof(vs)::Core.Const(Tuple{SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}})
│ %9 = Core.apply_type(%6, %7, %8)::Core.Const(var"#25#26"{SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, Tuple{SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}}})
│ %10 = v::SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}
│ (#25 = %new(%9, %10, vs))
│ %12 = #25::var"#25#26"{SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, Tuple{SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}}}
│ %13 = Core.apply_type(Main.NTuple, $(Expr(:static_parameter, 1)), Main.Int)::Core.Const(Tuple{Int64, Int64, Int64})
│ %14 = Main.altsigns(Main.Int)::Core.Const(Base.Iterators.Cycle{Tuple{Int64, Int64}}((1, -1)))
│ %15 = (%13)(%14)::Core.Const((1, -1, 1))
│ %16 = Main.swapeach_1st(inds)::Tuple{Tuple{Int64, Int64, Int64}, Tuple{Int64, Int64, Int64}, Tuple{Int64, Int64, Int64}}
│ %17 = Main.map(%12, %15, %16)::Tuple{Float64, Float64, Float64}
│ %18 = Core._apply_iterate(Base.iterate, Main.:+, %17)::Float64
└── return %18

```

and for the 4x4 case

```julia
julia> @code_warntype _det((1,2,3,4), NTuple{4}(eachcol(mat4x4)))

MethodInstance for _det(::NTuple{4, Int64}, ::NTuple{4, SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}})
  from _det(inds::Tuple{Vararg{Int64, N}}, ::Tuple{Vararg{Any, N}}) where N in Main at In[10]:7
Static Parameters
  N = 4
Arguments
  #self#::Core.Const(_det)
  inds::NTuple{4, Int64}
  @_3::NTuple{4, SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}}
Locals
  #23::var"#23#24"{SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, Tuple{SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}}}
  @_5::Int64
  v::SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}
  vs::Tuple{SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}}
Body::Any
1 ─ nothing
│ %2 = Base.indexed_iterate(@_3, 1)::Core.PartialStruct(Tuple{SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, Int64}, Any[SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, Core.Const(2)])
│ (v = Core.getfield(%2, 1))
│ (@_5 = Core.getfield(%2, 2))
│ (vs = Base.rest(@_3, @_5::Core.Const(2)))
│ %6 = Main.:(var"#23#24")::Core.Const(var"#23#24")
│ %7 = Core.typeof(v)::Core.Const(SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true})
│ %8 = Core.typeof(vs)::Core.Const(Tuple{SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}})
│ %9 = Core.apply_type(%6, %7, %8)::Core.Const(var"#23#24"{SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, Tuple{SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}}})
│ %10 = v::SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}
│ (#23 = %new(%9, %10, vs))
│ %12 = #23::var"#23#24"{SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, Tuple{SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}}}
│ %13 = Core.apply_type(Main.NTuple, $(Expr(:static_parameter, 1)), Main.Int)::Core.Const(NTuple{4, Int64})
│ %14 = Main.altsigns(Main.Int)::Core.Const(Base.Iterators.Cycle{Tuple{Int64, Int64}}((1, -1)))
│ %15 = (%13)(%14)::Core.Const((1, -1, 1, -1))
│ %16 = Main.swapeach_1st(inds)::NTuple{4, NTuple{4, Int64}}
│ %17 = Main.map(%12, %15, %16)::NTuple{4, Any}
│ %18 = Core._apply_iterate(Base.iterate, Main.:+, %17)::Any
└── return %18

```

---

<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:** [April 3, 2022, 3:49pm UTC](https://discourse.julialang.org/t/type-stability-of-recursive-functions/78946/2 "2022-04-03T15:49:41Z")

</div>

Looks fine for me on 1.9.0

```julia
using Static, ArrayInterface, BenchmarkTools

# Compute determinant of a matrix with equal-length row/column vectors `vs`
det(vs::Vararg{Any,N}) where N = _det(ntuple(identity, N), vs)

@inline _det((ind,)::NTuple{1,Int}, (v,)::NTuple{1,Any}) = getindex(v, ind)

@inline _det(inds::NTuple{N,Int}, (v, vs...)::NTuple{N,Any}) where N =
    +(map((sgn, (i, is...)) -> flipsign(v[i], sgn) * _det(is, vs),
          NTuple{N,Int}(altsigns(Int)), swapeach_1st(inds))...)

using Base.Iterators: map as imap
const CanonicalInt = Union{StaticInt, Int}

# Like `ntuple`, but uses `StaticInt`s
sntuple(f, n::StaticInt) = _sntuple(f, n, n)
_sntuple(_, ::StaticInt, ::StaticInt{0}) = ()
_sntuple(f, n::StaticInt, i::StaticInt) =
    (f(n - i + static(1)), _sntuple(f, n, i - static(1))...)

altsigns(init) = Iterators.cycle((init, -init))
altsigns(T::Type) = altsigns(oneunit(T))
# altsigns(Int) -> (1, -1, 1, -1, ...)

# Return the input tuple with the element at the index `i` swapped with the
# first element.
# julia> swap_1st(static(2), ('a', 'b', 'c'))
# ('b', 'a', 'c')
function swap_1st(i::StaticInt, tup::Tuple)
    N = ArrayInterface.static_length(tup)
    1 ≤ i ≤ N || return tup
    (tup[i], sntuple(j -> tup[j], i - static(1))...,
            sntuple(j -> tup[j+i], N - i)...)
end

# Return a tuple of tuples where the ith tuple swaps the 1st and i-th elements
# of the input tuple.
# julia> swapeach_1st(('a', 'b', 'c'))
# (('a', 'b', 'c'), ('b', 'a', 'c'), ('c', 'a', 'b'))
swapeach_1st(tup::NTuple{N,Any}) where {N} =
    sntuple(i -> swap_1st(i, tup), static(N))          

@btime det(NTuple{3}(eachcol(rand(3,3)))...) # type stable -> Float64
@btime det(NTuple{4}(eachcol(rand(4,4)))...)

@code_warntype det(NTuple{3}(eachcol(rand(3,3)))...) # type stable -> Float64
@code_warntype det(NTuple{4}(eachcol(rand(4,4)))...)

```

yields

```julia
  118.053 ns (1 allocation: 128 bytes)
  174.590 ns (1 allocation: 192 bytes)
MethodInstance for det(::SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, ::SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, ::SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true})
  from det(vs::Vararg{Any, N}) where N in Main at ...
Static Parameters
  N = 3
Arguments
  #self#::Core.Const(det)
  vs::Tuple{SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}}
Body::Float64
1 ─ %1 = Main.ntuple(Main.identity, $(Expr(:static_parameter, 1)))::Core.Const((1, 2, 3))
│ %2 = Main._det(%1, vs)::Float64
└── return %2

MethodInstance for det(::SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, ::SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, ::SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}, ::SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true})
  from det(vs::Vararg{Any, N}) where N in Main at ...
Static Parameters
  N = 4
Arguments
  #self#::Core.Const(det)
  vs::NTuple{4, SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}}
Body::Float64
1 ─ %1 = Main.ntuple(Main.identity, $(Expr(:static_parameter, 1)))::Core.Const((1, 2, 3, 4))
│ %2 = Main._det(%1, vs)::Float64
└── return %2

```

Edit: posted complete code and corrected results…

---

<div class="post-metadata">

**Author:** ![nchisholm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nchisholm/32/37414_2.png) [@nchisholm](https://discourse.julialang.org/u/nchisholm)\
**Post date:** [April 3, 2022, 4:00pm UTC](https://discourse.julialang.org/t/type-stability-of-recursive-functions/78946/3 "2022-04-03T16:00:23Z")

</div>

Thanks @goerch!

I think you should be getting a `Float64` return value, though. `det` expects each vector as a separate argument. (There’s a typo in my original post that I corrected but may have made things confusing.) Does

```julia
det(NTuple{4}(eachcol(rand(4,4)))...)

```

infer to a `Float64`?

I don’t have 1.9.0 installed, but that would be great news if there have been enhancements that allow this to work.

**Edit:** Thanks again @goerch 😀! Very cool that this works in `1.9.0`. Thankfully, for my potential application of this pattern, I only need the `2x2` and `3x3` cases (for now), so I can afford to wait for it.

I am wondering to what extent `@generated` functions, with their many gotchas, will be really needed in the future. It seems to me that you can do quite general “code generation” using just `@inline`, `ntuple`, `map`, and packages like `Static`.

BTW I tried things initially on `julia 1.7.2`. There, other functions with a recursive call to themselves made inside `map` seem to have similar issues — they seem to go type-unstable if 3 or more recursive calls occur.

---

<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:** [April 3, 2022, 7:43pm UTC](https://discourse.julialang.org/t/type-stability-of-recursive-functions/78946/4 "2022-04-03T19:43:28Z")

</div>

> [@nchisholm](#):
>
> Thankfully, for my potential application of this pattern, I only need the `2x2` and `3x3` cases (for now), so I can afford to wait for it.

In a real application, I would just use `SMatrix` from StaticArrays.jl, which [already has these cases built-in](https://github.com/JuliaArrays/StaticArrays.jl/blob/aa4b15511976774ae123b82b01bbde554de0f44e/src/det.jl#L8-L35).

---

<div class="post-metadata">

**Author:** ![nchisholm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nchisholm/32/37414_2.png) [@nchisholm](https://discourse.julialang.org/u/nchisholm)\
**Post date:** [April 10, 2022, 7:16pm UTC](https://discourse.julialang.org/t/type-stability-of-recursive-functions/78946/5 "2022-04-10T19:16:29Z")

</div>

Alright, I am still a little confused still after trying a simpler example than my original determinant problem. I tried using julia 1.7.2 as well as the nightly build and got the same results for the functions below.

The function `pop` returns the `i`th element of a tuple `xs` at position `i` and a new tuple with that element removed.

```julia
@inline pop(xs::Tuple, i::Integer) = _pop((), xs, i)
@inline _pop(out::Tuple, ::Tuple{}, i::Integer) = error("index out of bounds")
@inline _pop(out::Tuple, (x, xs...)::Tuple, i::Integer) =
    i == 1 ? (x, (out..., xs...)) : _pop((out..., x), xs, i-1)

```

It is type-stable only for input tuples of length three or fewer. Trying to apply it to longer tuples results in allocations.

An alternative approach somehow avoids the type instability (I tested on input tuples up to length 10), but I am not sure why.

```julia
@inline deleteat(xs::Tuple, i) =
@inline deleteat(::Tuple{}, i) = error("index out of bounds")
@inline deleteat((x, xs...)::Tuple, i=1) =
    i == 1 ? xs : (x, deleteat(xs, i-1)...)

pop2(xs::Tuple, i::Integer) =
    1 ≤ i ≤ length(xs) ? (xs[i], deleteat(xs, i)) : error("index out of bounds")

```

I guess I am just wondering if there are rules to be aware of here…

---

<div class="post-metadata">

**Author:** ![Elrod](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/elrod/32/22461_2.png) [@Elrod](https://discourse.julialang.org/u/Elrod)\
**Post date:** [April 11, 2022, 2:38am UTC](https://discourse.julialang.org/t/type-stability-of-recursive-functions/78946/6 "2022-04-11T02:38:20Z")

</div>

I asked a similar question earlier, and Shuhei suggested following the approach used here:  
[https://github.com/CliMA/ClimaCore.jl/blob/05da995b50486936a608677dafc8f46ecf0a11ed/src/Operators/finitedifference.jl#L2147-L2155](https://github.com/CliMA/ClimaCore.jl/blob/05da995b50486936a608677dafc8f46ecf0a11ed/src/Operators/finitedifference.jl#L2147-L2155)  
which solved the problem in my case.  
Except he suggested using `@nospecialize(args...)`.

---

<div class="post-metadata">

**Author:** ![jt1](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jt1/32/38331_2.png) [@jt1](https://discourse.julialang.org/u/jt1)\
**Post date:** [May 1, 2023, 1:05pm UTC](https://discourse.julialang.org/t/type-stability-of-recursive-functions/78946/7 "2023-05-01T13:05:12Z")

</div>

That solution doesn’t seem to work for me on 1.8.5. Because the `recursion_limit` also is triggered on functions in `Base` that you likely don’t want to change the `recursion_limit` property on. Any suggestions?

Note:

- had to change `ArrayInterface.static_length(tup)` to `static(ArrayInterface.length(tup))`
- The limit of inferrable compilation for me is `N=5`.

```julia
using Static, ArrayInterface, BenchmarkTools

# Compute determinant of a matrix with equal-length row/column vectors `vs`
det(vs::Vararg{Any,N}) where {N} = _det(ntuple(identity, N), vs)

@inline _det((ind,)::NTuple{1,Int}, (v,)::NTuple{1,Any}) = getindex(v, ind)

@inline _det(inds::NTuple{N,Int}, (v, vs...)::NTuple{N,Any}) where {N} =
    +(map((sgn, (i, is...)) -> flipsign(v[i], sgn) * _det(is, vs),
        NTuple{N,Int}(altsigns(Int)), swapeach_1st(inds))...)

if hasfield(Method, :recursion_relation)
    dont_limit = (args...) -> true
    for m in methods(_det)
        m.recursion_relation = dont_limit
    end
end

using Base.Iterators: map as imap
const CanonicalInt = Union{StaticInt,Int}

# Like `ntuple`, but uses `StaticInt`s
sntuple(f, n::StaticInt) = _sntuple(f, n, n)
_sntuple(_, ::StaticInt, ::StaticInt{0}) = ()
_sntuple(f, n::StaticInt, i::StaticInt) =
    (f(n - i + static(1)), _sntuple(f, n, i - static(1))...)

altsigns(init) = Iterators.cycle((init, -init))
altsigns(T::Type) = altsigns(oneunit(T))
# altsigns(Int) -> (1, -1, 1, -1, ...)

# Return the input tuple with the element at the index `i` swapped with the
# first element.
# julia> swap_1st(static(2), ('a', 'b', 'c'))
# ('b', 'a', 'c')
function swap_1st(i::StaticInt, tup::Tuple)
    N = static(ArrayInterface.length(tup))
    1 ≤ i ≤ N || return tup
    (tup[i], sntuple(j -> tup[j], i - static(1))...,
        sntuple(j -> tup[j+i], N - i)...)
end

# Return a tuple of tuples where the ith tuple swaps the 1st and i-th elements
# of the input tuple.
# julia> swapeach_1st(('a', 'b', 'c'))
# (('a', 'b', 'c'), ('b', 'a', 'c'), ('c', 'a', 'b'))
swapeach_1st(tup::NTuple{N,Any}) where {N} = sntuple(i -> swap_1st(i, tup), static(N))

using BenchmarkTools
@btime det(NTuple{5}(eachcol(rand(5, 5)))...)
@btime det(NTuple{6}(eachcol(rand(6, 6)))...)

@code_warntype det(NTuple{5}(eachcol(rand(5, 5)))...)
@code_warntype det(NTuple{6}(eachcol(rand(6, 6)))...)

using JET
@report_opt det(NTuple{6}(eachcol(rand(6, 6)))...)

```

The `JET.@report_opt` call shows the functions that throw “failed to optimize due to recursion”, among which functions from `Base`.