# Recursively applied 1D function

Hello,

I am trying to compose the same function with itself n times efficiently. I found a way of doing that using macros, but it gave me a lot of problems when being used within functions and using elements that were not parts of the global scope. So, an example that was working well, before using it in a local scope was:

``````macro recur(map_name, iter_num, val_input)
eval(Meta.parse(string(string(map_name, "(")^iter_num, val_input, ")"^iter_num)))
end
``````

and then using, for instance:

``````g(x) = x^2

@recur g 10 1.001
``````

which yields: `2.7828855056543795`. I also did a similar thing using a function, but the core concept remains the same.

My question is: What would be a better way of doing this? Is there some built-in way of manipulating composition of function, without having to write up explicitly the composition, like `g(g(g(g(g(g(g(g(g(g(1.001))))))))))` or `(g∘g∘g∘g∘g∘g∘g∘g∘g∘g)(1.001)`?

Thanks!

The first note I’d make is that it’s ~never necessary to use string manipulation, `eval`, or `Meta.parse` inside a macro. One of the many reasons not to use `eval` in particular is that it causes your code to be run when the macro is expanded, which is almost never what you want:

``````julia> macro recur(map_name, iter_num, val_input)
eval(Meta.parse(string(string(map_name, "(")^iter_num, val_input, ")"^iter_num)))
end
@recur (macro with 1 method)

julia> f() = @recur g 10 1.001
ERROR: LoadError: UndefVarError: g not defined
``````

This fails (in a new Julia session) because `eval` tries to call `g(...)` when you define `f`, which is definitely wrong.

Fortunately, it’s easy to avoid strings, `eval` and `Meta.parse` because Julia’s built-in expression objects are much easier to work with. A macro similar to yours but with none of those red flags might be:

``````julia> macro recur(map_name, iter_num, val_input)
for i in 2:iter_num
expr = :(\$(esc(map_name)) ∘ \$expr)  # turn `f` into `f \circ f`
end
return quote # return an expression which computes the result
\$(expr)(\$(esc(val_input)))
end
end
@recur (macro with 1 method)
``````

However, I don’t really think there’s any need for metaprogamming here at all. Instead, I’d just write a function:

``````julia> function recur(f, iter_num, val)
@assert iter_num >= 1
output = f(val)
for i in 2:iter_num
output = f(output)
end
return output
end
recur (generic function with 1 method)

julia> g(x) = x^2
g (generic function with 1 method)

julia> recur(g, 10, 1.001)
2.7828855056543795
``````

Or, if you want something without a loop, then we can use, well, recursion…

``````julia> function recur(f, iter_num, val)
@assert iter_num >= 1
if iter_num == 1
f(val)
else
f(recur(f, iter_num - 1, val))
end
end
recur (generic function with 1 method)

julia> g(x) = x^2
g (generic function with 1 method)

julia> recur(g, 10, 1.001)
2.7828855056543795
``````
3 Likes

Note that `∘` accepts any number of arguments, so you can do this (even if you probably shouldn’t):

``````julia> Base.:^(f::Function, n::Int) = ∘(ntuple(_ -> f, n)...)

julia> sin^3
sin ∘ sin ∘ sin

julia> ((!)^17)(true)
false
``````
2 Likes

This great post by @FedericoStra, might be of interest.
Applying it to OP’s case:

``````g(x) = x^2
Gn(x, n) = foldl((y,_) -> g(y), 1:n; init=x)
Gn(1.001, 10)
2.7828855056543795
``````
2 Likes