Anonymous recursion

In computer science, anonymous recursion is a recursion technique that uses anonymous functions.

Construction

Suppose that f is an n-argument recursive function defined in terms of itself:

$f(x_{1},x_{2},\dots ,x_{n}):={\mbox{expression in terms of }}x_{1},x_{2},\dots ,x_{n}{\mbox{ and }}f(\dots ).$

We want to define an equivalent recursive anonymous function $f^{*}$ which is not defined in terms of itself. One possible procedure is the following:

1. Define a (n + 1)-argument function h like f, except that h takes one extra argument, which is the function f itself. (Function h inherits its first n arguments from f.)
2. Change f, the last argument of h, from an n-argument function to an (n + 1)-argument function by feeding f to itself as f′s last argument for all instances of f within the definition of h. (This puts function h and its last argument f on an equal footing.) The functions f and h are now defined by

   $f(x_{1},x_{2},\dots ,x_{n},f):={\mbox{expression in terms of }}x_{1},x_{2},\dots ,x_{n}{\mbox{ and }}f(\dots ,f).$

   $h(x_{1},x_{2},\dots ,x_{n},f):={\mbox{expression in terms of }}x_{1},x_{2},\dots ,x_{n}{\mbox{ and }}f(\dots ,f).$

3. Pass on h to itself as h's own last argument, and let this be the definition of the desired n-argument recursive anonymous function $f^{*}$:

   $f^{*}(x_{1},x_{2},\dots ,x_{n}):=h(x_{1},x_{2},\dots ,x_{n},h)\$

Example

Given

$f(x):={\begin{cases}1&{\mbox{if}}\ x=0\\x\cdot f(x-1)&{\mbox{otherwise}}\end{cases}}$

The function f is defined in terms of itself: such circular definitions are not allowed in anonymous recursion (because functions are not bound to labels). To start with a solution, define a function h(x,f) in exactly the same way that f(x) was defined above:

$h(x,f):={\begin{cases}1&{\mbox{if}}\ x=0\\x\cdot f(x-1)&{\mbox{otherwise}}\end{cases}}$

Second step: change $f(x-1)$ in the definition to $f(x-1,f)$:

$h(x,f):={\begin{cases}1&{\mbox{if}}\ x=0\\x\cdot f(x-1,f)&{\mbox{otherwise}}\end{cases}}$

so that the function f passed on to h will have the same number of arguments as h itself.

Third step: the factorial function $f^{*}$ of x can now be defined as:

$f^{*}(x):=h(x,h).\,$

Relation to the use of the Y combinator

The above approach to constructing anonymous recursion differs, but is related to, the use of fixed point combinators. To see how they are related, perform a variation of the above steps. Starting from the recursive definition (using the language of lambda calculus):

${\bar {f}}:=(\lambda n.\,{\mbox{if}}(n=0,1,n\cdot {\bar {f}}(n-1))).$

First step,

${\bar {h}}:=(\lambda f.\lambda n.\,{\mbox{if}}(n=0,1,n\cdot f(n-1))).$

Second step,

${\bar {g}}:=(\lambda g.\lambda n.\ {\mbox{if}}(n=0,1,n\cdot g(g)(n-1)))$

where $g(g)(n-1)\equiv g(g,n-1)$. Note that the variation consists of defining ${\bar {g}}$ in terms of $g(g,n-1)$ instead of in terms of $g(n-1,g)$.

Third step: let a "Z combinator" be defined by

$Z:=(\lambda g.\ (g\ g))$

such that

${\bar {f}}^{*}:=Z{\bar {g}}.$

Here, ${\bar {g}}$ is passed to itself right before a number is fed to it, so ${\bar {f}}^{*}n\equiv n!$ for any Church number n.

Note that $g\ (g)\ n\equiv (g\ (g))\ n\equiv (g\ g)\ n$, i.e. $g(g)\equiv (gg)$.

Now an extra fourth step: notice that

${\bar {g}}\equiv (\lambda g.\ {\bar {h}}\ (g\ g))$

(see first and second steps) so that

${\bar {f}}^{*}\equiv (\lambda .\,g\ (g\ g))(\lambda g.\,{\bar {h}}\ (g\ g))$

$\equiv (\lambda h.\,(\lambda g.\,(g\ g))(\lambda g.\,h\ (g\ g)))\ {\bar {h}}.$

Let the Y combinator be defined by

$Y:=(\lambda h.\,(\lambda g.\,h\ (g\ g))(\lambda g.\,h\ (g\ g)))$

so that

$Z{\bar {g}}\equiv Y{\bar {h}}.$

External links

• The Lambda Calculus: notes by Don Blaheta (PDF file). See the section titled "What's left? Recursion", for the genesis of the Y combinator.