<p>You may replace recursion with computation of fixed points, so all you need is a fixed-point operator</p>

<pre><code>fix : (a -&gt; a) -&gt; a
</code></pre>

<p>which satisfies</p>

<pre><code>fix f = f (fix f)
</code></pre>

<p>Then, given a recursive definition of <code>f : a -&gt; b</code>,</p>

<pre><code>f = Φ(f)
</code></pre>

<p>we may define <code>f</code> as</p>

<pre><code>f = fix (λg.Φ(g))
</code></pre>

<p>Here <code>fix</code> has type <code>((a -&gt; b) -&gt; (a -&gt; b)) -&gt; (a -&gt; b)</code>.</p>

<p>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.</p>

CC BY-SA 3.0
2016-12-09T16:35:49.827Z
Thank you! I studied this about 8 years ago, and since I haven't looked at he subject since I had indeed forgotten the connection. Maybe I'll return when I've figured out what I'm really trying to ask, but this answer is definitely the starting point I was looking for.
HillwoodMonkey
CC BY-SA 3.0
2016-12-09T07:13:46.860Z
2016-12-09T07:13:46.860Z
Andrej Bauer
<p>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.</p>

<p>If recursion <em>can</em> 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.</p>

<p>Apologies if this question is ill-formed. I'm no PLT expert.</p>

CC BY-SA 3.0
2016-12-09T01:41:44.783Z
Are you looking for Kleene normal form?
François G. Dorais
CC BY-SA 3.0
2016-12-09T03:00:44.943Z
You could always use the [Y combinator](https://en.wikipedia.org/wiki/Fixed-point_combinator#Fixed_point_combinators_in_lambda_calculus) which is sufficient to simulate all recursion...
cody
CC BY-SA 3.0
2016-12-09T07:10:46.680Z
Does it matter that `fold`, `map`, `filter`, etc. are themselves defined by (structural) recursion? And would you consider it cheating if I suggested that all you need is `fix : (t -> t) -> t` which computes fixed points?
Andrej Bauer
CC BY-SA 3.0
2016-12-09T07:15:33.297Z
Can we migrate this to cs.computerscience.com?
Andrej Bauer
CC BY-SA 3.0
2016-12-09T16:42:42.840Z
I am not sure about Kleene normal form, but the others were correct to guess that I was lacking basic knowledge about fixed-point combinators. Incidentally, I don't care whether or not the higher order functions are defined by structural recursion. But I'm going to go away and read more before thinking about this. Thanks guys.
HillwoodMonkey
CC BY-SA 3.0
2016-12-09T16:48:00.830Z
Also I don't know what cs.computerscience.com is, or whether that question was addressed to me.
HillwoodMonkey
CC BY-SA 3.0
2016-12-10T08:24:30.357Z
Oops, I meant cs.stackexchange.com.
Andrej Bauer
<pl.programming-languages><lambda-calculus>
Can recursion be replaced with a finite set of higher-order functions?
HillwoodMonkey
# Can recursion be replaced with a finite set of higher-order functions?

(Asked by: username_0 on 2016-12-08)

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.

**Tags:** pl.programming-languages, lambda-calculus
> **Comments:**
> **username_1**: Are you looking for Kleene normal form?  
> **username_2**: You could always use the [Y combinator](https://en.wikipedia.org/wiki/Fixed-point_combinator#Fixed_point_combinators_in_lambda_calculus) which is sufficient to simulate all recursion...  
> **username_3**: Does it matter that `fold`, `map`, `filter`, etc. are themselves defined by (structural) recursion? And would you consider it cheating if I suggested that all you need is `fix : (t -> t) -> t` which computes fixed points?  
> **username_3**: Can we migrate this to cs.computerscience.com?  
> **username_0**: I am not sure about Kleene normal form, but the others were correct to guess that I was lacking basic knowledge about fixed-point combinators. Incidentally, I don't care whether or not the higher order functions are defined by structural recursion. But I'm going to go away and read more before thinking about this. Thanks guys.  
> **username_0**: Also I don't know what cs.computerscience.com is, or whether that question was addressed to me.  
> **username_3**: Oops, I meant cs.stackexchange.com.  

---

## 1 answers

### Answer by username_3 on 2016-12-09. Score: 6 | Accepted answer

You may replace recursion with computation of fixed points, so all you need is a fixed-point operator
fix : (a -> a) -> a

which satisfies
fix f = f (fix f)

Then, given a recursive definition of f : a -> b,
f = Φ(f)

we may define f as
f = fix (λg.Φ(g))

Here fix has type ((a -> b) -> (a -> b)) -> (a -> 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.

> **Comments:**
> **username_0**: Thank you! I studied this about 8 years ago, and since I haven't looked at he subject since I had indeed forgotten the connection. Maybe I'll return when I've figured out what I'm really trying to ask, but this answer is definitely the starting point I was looking for.  

---

