- Anonymous recursion
In
computer science , anonymous recursion is a recursion technique that usesanonymous function s.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:f(x):= egin{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) := egin{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):=egin{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 combinator s. To see how they are related, perform a variation of the above steps. Starting from the recursive definition (using the language oflambda calculus )::ar f := (lambda n. , mbox{if}(n = 0, 1, n cdot ar f (n - 1))).
First step,
:ar h:= (lambda f. lambda n. , mbox{if} (n = 0, 1, n cdot f (n - 1))).
Second step,
:ar 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 ar 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
:ar f^* := Z ar g.
Here, ar g is passed to itself right before a number is fed to it, so ar 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 (g g).
Now an extra fourth step: notice that
:ar g equiv (lambda g. ar h (g g))
(see first and second steps) so that
:ar f^* equiv (lambda. , g (g g)) (lambda g. , ar h (g g))
::equiv (lambda h. , (lambda g., (g g)) (lambda g., h (g g))) ar h.
Let the "Y" combinator be defined by
:Y:= (lambda h. , (lambda g., h (g g)) (lambda g., h (g g)))
so that
:Z ar g equiv Y ar h.
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."
Wikimedia Foundation. 2010.