Anonymous recursion

From Wikipedia, the free encyclopedia

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

1 Construction
2 Example
3 Relation to the use of the Y combinator
4 External links

[edit] 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) \$

[edit] 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). \,$

[edit] 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)$ .