Anonymous recursion refers to the construction and existence of anonymously recursive functions. Given an n-argument recursive function f defined in terms of itself, it is possible to define an equivalent recursive anonymous function f ^* which is not defined in terms of itself. One possible procedure is the following: In mathematical logic and computer science, the recursive functions are a class of functions from natural numbers to natural numbers which are computable in some intuitive sense. ...

1. Define an (n+1)-argument function h in terms of f the same way that f was defined in terms of itself, and let h′s last argument be f. (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.)
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 ^* :

where

in terms of

in the same way as

in terms of

Example

Given

The function f is defined in terms of itself: such circular definitions are not allowed in anonymous recursion (becase 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): A fixed point combinator is a function which computes fixed points of other functions. ... The lambda calculus is a formal system designed to investigate function definition, function application, and recursion. ...

First step,

Second step,

where . 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

such that

.

Here, is passed to itself right before a number is fed to it, so for any Church number n. A Church integer is a representation of natural numbers as functions, invented by Alonzo Church as part of his lambda calculus. ...

Note that , i.e. .

Now an extra fourth step: notice that

(see first and second steps) so that

.

Let the Y combinator be defined by

so that

.

See also

• lambda calculus

The lambda calculus is a formal system designed to investigate function definition, function application, and recursion. ...

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.