Recursive closures/inner functions -- how to avoid boxing?

General Usage
,
7

The easiest way is to just pass the function to itself. Instead of the walkdir example, I’ll show fib:

julia> let
           # Create a local function _fib whose first argument is a function fib
           function _fib(fib, n) 
               if n <= 1
                   return n
               else
                   # inside _fib, we recurse using fib, *not* _fib
                   fib(fib, n-1) + fib(fib, n-2)
               end
           end
           # now create a new local function fib that calls _fib(_fib, n)
           fib(n) = _fib(_fib, n)
       end
(::var"#fib#18"{var"#_fib#17"}) (generic function with 1 method)

julia> @btime $ans(10)
  212.570 ns (0 allocations: 0 bytes)
55

I showed a macro in Performant Recursive Anonymous Functions - #17 by Mason that automates this process:

using ExprTools: splitdef, combinedef
using MacroTools: postwalk, @capture

"""
This is only worth using for locally scoped recursive functions.
"""
macro fast_recursion(fdef)
    d = splitdef(fdef)
    name = get!(d, :name, gensym(:f))
    fargs = copy(get!(d, :args, []))
    fkwargs = get!(d, :kwargs, [])
    _name = gensym(name)
    __name = gensym(Symbol(:_, name))
    d[:body] = postwalk(d[:body]) do ex
        if @capture(ex, f_(args__))
            if f == name
                return :($__name($__name, $(args...),))
            end
        elseif @capture(ex, f(args__; kwargs__))
            if f == name
                return :($__name($__name, $(args...); $(kwargs...),))
            end
        end
        ex
    end
    d[:name] = _name
    d[:args] = pushfirst!(d[:args], __name)
    quote
        $(combinedef(d))
        $name($(fargs...); $(fkwargs...),) = $_name($_name, $(fargs...); $(fkwargs...),)
    end |> esc
end

and then we see

julia> @btime let
           fib(n) = n ≤ 1 ? n : fib(n-1) + fib(n-2)
           fib(10)
       end
  2.620 μs (2 allocations: 32 bytes)
55

julia> @btime let
           @fast_recursion fib(n) = n ≤ 1 ? n : fib(n-1) + fib(n-2)
           fib(10)
       end
  212.815 ns (0 allocations: 0 bytes)
55

Docs to improve walkdir and the performance tips would be a great idea!

And if someone wants to put @fast_recursion into a little package and register it, you’d certainly have my blessing (as with any code code I post here or other julia help channels)

2 Likes