How to return self recursive function?

General Usage
, ,
3

Not sure whether there would be an easier approach, but recursive behavior is not to hard to obtain if you replace the closure by an explicit callable struct (which is what would happen under the hood anyway, but by doing it yourself you gain more control).

Using a recurrence relation of the form specified in the OP seems tricky though. In the code below, I “cheat” by defining the recurrence relation in a (IMO) more explicitly way, in which the function arity corresponds to the recurrence order:

# This struct explicitly defines the state of your function object
# (previously, it was the variables that the closure captures)
struct RecSeq{N,T,U}
    a    :: U
    init :: NTuple{N,T}
end

# This defines the behavior of `RecSeq` as a callable object
# (previously, it was the closure body)
function (f::RecSeq{N})(n) where {N}
    n < N && return f.init[n+1]
    u = ntuple(Val(N)) do k # the function object is naturally named
        f(n-k)              # which makes it easy for it to recursively
    end                     # "call" itself
    a(u...)
end

julia> a(uₙ₋₁, uₙ₋₂) = uₙ₋₁ + uₙ₋₂
a (generic function with 1 method)

julia> fib = RecSeq(a, (0,1))
RecSeq{2, Int64, typeof(a)}(a, (0, 1))

julia> fib.(0:10)
11-element Vector{Int64}:
  0
  1
  1
  2
  3
  5
  8
 13
 21
 34
 55

(Of course you’d probably be much better off if you memoized the computation in this case, but I’m assuming your real use case is different…)

1 Like