Jump to content

Anonymous recursion

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by AugPi (talk | contribs) at 15:21, 2 November 2005 (new article). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

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. The procedure is the following:

  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