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

**URL:** https://discourse.julialang.org/t/recursive-closures-inner-functions-how-to-avoid-boxing/124758
**Category:** General Usage
**Tags:** question, closure
**Created:** [January 14, 2025, 10:34am UTC](https://discourse.julialang.org/t/recursive-closures-inner-functions-how-to-avoid-boxing/124758 "2025-01-14T10:34:21Z")
**Posts on this page:** 1
**Showing post:** 7

<div class="post-metadata">

### Author: ![Mason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mason/32/2423_2.png) [@Mason](https://discourse.julialang.org/u/Mason)
#### Post date: [January 14, 2025, 1:40pm UTC](https://discourse.julialang.org/t/recursive-closures-inner-functions-how-to-avoid-boxing/124758/7 "2025-01-14T13:40:28Z")

</div>

> [@foobar\_lv2](#):
>
> Given today’s compiler, what is today’s idiomatic way of expressing `Base.walkdir` (linked above)?
> 
> Is it “don’t do recursive inner functions, use an explicit callable struct”?
> 
> That is something we should
> 
> 1. explain in the performance tips
> 2. apply to `walkdir` in `Base/file.jl` etc (what’s good for the goose is good for the gander)

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

```julia-repl
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](https://discourse.julialang.org/t/performant-recursive-anonymous-functions/90984/17) that automates this process:

```julia
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-repl
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)

---

_[View the full topic](https://discourse.julialang.org/t/recursive-closures-inner-functions-how-to-avoid-boxing/124758)._