Can recursion be replaced with a finite set of higher-order functions? I am wondering if there is some proof that all recursive algorithms can be rewritten to use some known set of higher-order functions instead of recursion. I'm talking about functions like fold, map, filter, etc.

If recursion can always be replaced, I'm also interested in knowing whether there is some mechanical translation, or if it's something that can't be automated.

Apologies if this question is ill-formed. I'm no PLT expert.
You may replace recursion with computation of fixed points, so all you need is a fixed-point operator

fix : (a -&gt; a) -&gt; a


which satisfies

fix f = f (fix f)


Then, given a recursive definition of f : a -&gt; b,

f = Φ(f)


we may define f as

f = fix (λg.Φ(g))


Here fix has type ((a -&gt; b) -&gt; (a -&gt; b)) -&gt; (a -&gt; b).

You may consider this to be cheating, but the question is not really research-level precisely because the connection between recursion and fixed points is a basic piece of knowledge. I am guessing that maybe you did not know about the connection.