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:
# 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".)
# 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).$
# 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: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::

Second step: change $f(x\; -\; 1)$ in the definition to $f(x\; -\; 1,\; f)$::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):

:

First step,

:

Second step,

:

where $g\; (g)\; (n\; -\; 1)\; equiv\; g\; (g,\; n\; -\; 1)$. Note that the variation consists of defining 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

:

Here, is passed to itself right before a number is fed to it, so for any Church number "n".

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

Now an extra fourth step: notice that

:

(see first and second steps) so that

:

::

Let the "Y" combinator be defined by

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

so that

:

External links

* [http://www.cs.brown.edu/courses/cs173/2001/Lectures/2001-10-25.pdf The Lambda Calculus: notes by Don Blaheta] (PDF file). "See the section titled "What's left? Recursion", for the genesis of the Y combinator."