HOME

TheInfoList



OR:

In
computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, anonymous recursion is
recursion Recursion occurs when the definition of a concept or process depends on a simpler or previous version of itself. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in m ...
which does not explicitly call a function by name. This can be done either explicitly, by using a
higher-order function In mathematics and computer science, a higher-order function (HOF) is a function that does at least one of the following: * takes one or more functions as arguments (i.e. a procedural parameter, which is a parameter of a procedure that is itself ...
– passing in a function as an argument and calling it – or implicitly, via reflection features which allow one to access certain functions depending on the current context, especially "the current function" or sometimes "the calling function of the current function". In programming practice, anonymous recursion is notably used in
JavaScript JavaScript (), often abbreviated as JS, is a programming language and core technology of the World Wide Web, alongside HTML and CSS. Ninety-nine percent of websites use JavaScript on the client side for webpage behavior. Web browsers have ...
, which provides reflection facilities to support it. In general programming practice, however, this is considered poor style, and recursion with named functions is suggested instead. Anonymous recursion via explicitly passing functions as arguments is possible in any language that supports functions as arguments, though this is rarely used in practice, as it is longer and less clear than explicitly recursing by name. In theoretical computer science, anonymous recursion is important, as it shows that one can implement recursion without requiring named functions. This is particularly important for the
lambda calculus In mathematical logic, the lambda calculus (also written as ''λ''-calculus) is a formal system for expressing computability, computation based on function Abstraction (computer science), abstraction and function application, application using var ...
, which has anonymous unary functions, but is able to compute any recursive function. This anonymous recursion can be produced generically via
fixed-point combinator In combinatory logic for computer science, a fixed-point combinator (or fixpoint combinator) is a higher-order function (i.e., a function which takes a function as argument) that returns some '' fixed point'' (a value that is mapped to itself) of ...
s.


Use

Anonymous recursion is primarily of use in allowing recursion for
anonymous function In computer programming, an anonymous function (function literal, expression or block) is a function definition that is not bound to an identifier. Anonymous functions are often arguments being passed to higher-order functions or used for const ...
s, particularly when they form closures or are used as callbacks, to avoid having to bind the name of the function. Anonymous recursion primarily consists of calling "the current function", which results in direct recursion. Anonymous indirect recursion is possible, such as by calling "the caller (the previous function)", or, more rarely, by going further up the
call stack In computer science, a call stack is a Stack (abstract data type), stack data structure that stores information about the active subroutines and block (programming), inline blocks of a computer program. This type of stack is also known as an exe ...
, and this can be chained to produce mutual recursion. The
self-reference Self-reference is a concept that involves referring to oneself or one's own attributes, characteristics, or actions. It can occur in language, logic, mathematics, philosophy, and other fields. In natural or formal languages, self-reference ...
of "the current function" is a functional equivalent of the " this" keyword in
object-oriented programming Object-oriented programming (OOP) is a programming paradigm based on the concept of '' objects''. Objects can contain data (called fields, attributes or properties) and have actions they can perform (called procedures or methods and impl ...
, allowing one to refer to the current context. Anonymous recursion can also be used for named functions, rather that calling them by name, say to specify that one is recursing on the current function, or to allow one to rename the function without needing to change the name where it calls itself. However, as a matter of
programming style Programming style, also known as coding style, are the conventions and patterns used in writing source code, resulting in a consistent and readable codebase. These conventions often encompass aspects such as indentation, naming conventions, cap ...
this is generally not done.


Alternatives


Named functions

The usual alternative is to use named functions and named recursion. Given an anonymous function, this can be done either by binding a name to the function, as in named function expressions in JavaScript, or by assigning the function to a variable and then calling the variable, as in function statements in JavaScript. Since languages that allow anonymous functions generally allow assigning these functions to variables (if not first-class functions), many languages do not provide a way to refer to the function itself, and explicitly reject anonymous recursion; examples include Go. For example, in JavaScript the factorial function can be defined via anonymous recursion as such:answer
by olliej, Oct 25 '08 to
Why was the arguments.callee.caller property deprecated in JavaScript?
, ''StackOverflow''
, 2, 3, 4, 5map(function(n) ); Rewritten to use a named function expression yields: , 2, 3, 4, 5map(function factorial(n) );


Passing functions as arguments

Even without mechanisms to refer to the current function or calling function, anonymous recursion is possible in a language that allows functions as arguments. This is done by adding another parameter to the basic recursive function and using this parameter as the function for the recursive call. This creates a higher-order function, and passing this higher function ''itself'' allows anonymous recursion within the actual recursive function. This can be done purely anonymously by applying a
fixed-point combinator In combinatory logic for computer science, a fixed-point combinator (or fixpoint combinator) is a higher-order function (i.e., a function which takes a function as argument) that returns some '' fixed point'' (a value that is mapped to itself) of ...
to this higher order function. This is mainly of academic interest, particularly to show that the lambda calculus has recursion, as the resulting expression is significantly more complicated than the original named recursive function. Conversely, the use of fixed-pointed combinators may be generically referred to as "anonymous recursion", as this is a notable use of them, though they have other applications.The If Work
Deriving the Y combinator
January 10th, 2008
This is illustrated below using Python. First, a standard named recursion: def fact(n): if n

0: return 1 return n * fact(n - 1)
Using a higher-order function so the top-level function recurses anonymously on an argument, but still needing the standard recursive function as an argument: def fact0(n0): if n0

0: return 1 return n0 * fact0(n0 - 1) fact1 = lambda f, n1: 1 if n1

0 else n1 * f(n1 - 1) fact = lambda n: fact1(fact0, n)
We can eliminate the standard recursive function by passing the function argument into the call: fact1 = lambda f, n1: 1 if n1

0 else n1 * f(f, n1 - 1) fact = lambda n: fact1(fact1, n)
The second line can be replaced by a generic
higher-order function In mathematics and computer science, a higher-order function (HOF) is a function that does at least one of the following: * takes one or more functions as arguments (i.e. a procedural parameter, which is a parameter of a procedure that is itself ...
called a '' combinator:'' F = lambda f: (lambda x: f(f, x)) fact1 = lambda f, n1: 1 if n1

0 else n1 * f(f, n1 - 1) fact = F(fact1)
Written anonymously: (lambda f: (lambda x: f(f, x))) \ (lambda g, n1: 1 if n1

0 else n1 * g(g, n1 - 1))
In the
lambda calculus In mathematical logic, the lambda calculus (also written as ''λ''-calculus) is a formal system for expressing computability, computation based on function Abstraction (computer science), abstraction and function application, application using var ...
, which only uses functions of a single variable, this can be done via the ''
Y combinator Y Combinator, LLC (YC) is an American technology startup accelerator and venture capital firm launched in March 2005 which has been used to launch more than 5,000 companies. The accelerator program started in Boston and Mountain View, Californi ...
.'' First make the higher-order function of two variables be a function of a single variable, which directly returns a function, by
currying In mathematics and computer science, currying is the technique of translating a function that takes multiple arguments into a sequence of families of functions, each taking a single argument. In the prototypical example, one begins with a functi ...
: fact1 = lambda f: (lambda n1: 1 if n1

0 else n1 * f(f)(n1 - 1)) fact = fact1(fact1)
There are two "applying a higher order function to itself" operations here: f(f) in the first line and fact1(fact1) in the second. Factoring out the second double application into a '' combinator'' yields: C = lambda x: x(x) fact1 = lambda f: (lambda n1: 1 if n1

0 else n1 * f(f)(n1 - 1)) fact = C(fact1)
Factoring out the other double application yields: C = lambda x: x(x) D = lambda f: (lambda x: f(lambda v: x(x)(v))) fact1 = lambda g: (lambda n1: 1 if n1

0 else n1 * g(n1 - 1)) fact = C(D(fact1))
Combining the two combinators into one yields the
Y combinator Y Combinator, LLC (YC) is an American technology startup accelerator and venture capital firm launched in March 2005 which has been used to launch more than 5,000 companies. The accelerator program started in Boston and Mountain View, Californi ...
: C = lambda x: x(x) D = lambda f: (lambda x: f(lambda v: x(x)(v))) Y = lambda y: C(D(y)) fact1 = lambda g: (lambda n1: 1 if n1

0 else n1 * g(n1 - 1)) fact = Y(fact1)
Expanding out the Y combinator yields: Y = lambda f: (lambda x: f(lambda v: x(x)(v))) \ (lambda x: f(lambda v: x(x)(v))) fact1 = lambda g: (lambda n1: 1 if n1

0 else n1 * g(n1 - 1)) fact = Y(fact1)
Combining these yields a recursive definition of the factorial in lambda calculus (anonymous functions of a single variable): (lambda f: (lambda x: f(lambda v: x(x)(v))) (lambda x: f(lambda v: x(x)(v)))) \ (lambda g: (lambda n1: 1 if n1

0 else n1 * g(n1 - 1)))


Examples


APL

In APL, the current dfn is accessible via . This allows anonymous recursion, such as in this implementation of the factorial: 5 120 ¨ ⍳10 ⍝ applied to each element of 0 to 9 1 1 2 6 24 120 720 5040 40320 362880


JavaScript

In
JavaScript JavaScript (), often abbreviated as JS, is a programming language and core technology of the World Wide Web, alongside HTML and CSS. Ninety-nine percent of websites use JavaScript on the client side for webpage behavior. Web browsers have ...
, the current function is accessible via arguments.callee, while the calling function is accessible via arguments.caller. These allow anonymous recursion, such as in this implementation of the factorial: , 2, 3, 4, 5map(function(n) );


Perl

Starting with
Perl Perl is a high-level, general-purpose, interpreted, dynamic programming language. Though Perl is not officially an acronym, there are various backronyms in use, including "Practical Extraction and Reporting Language". Perl was developed ...
5.16, the current subroutine is accessible via the __SUB__ token, which returns a reference to the current subroutine, or undef outside a subroutine. This allows anonymous recursion, such as in the following implementation of the factorial: #!/usr/bin/env perl use feature ":5.16"; print sub ->(5), "\n";


R

In R, the current function can be called using Recall. For example, sapply(0:5, function(n) ) It will not work, however, if passed as an argument to another function, e.g. lapply, inside the anonymous function definition. In this case, sys.function(0) can be used.agstudy's answer
t
Get currently called function to write anonymous recursive function
at ''StackOverflow''
For example, the code below squares a list recursively: (function(x) )(list(list(1, 2, 3), list(4, 5)))


References

{{reflist Recursion Articles with example JavaScript code Articles with example Python (programming language) code Articles with example R code