In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...
, anonymous recursion is
recursion
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematic ...
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 itse ...
– 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 that is one of the core technologies of the World Wide Web, alongside HTML and CSS. As of 2022, 98% of Website, websites use JavaScript on the Client (computing), client side ...
, 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
Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation t ...
, which has anonymous unary functions, but is able to compute any recursive function. This anonymous recursion can be produced generically via
fixed-point combinators.
Use
Anonymous recursion is primarily of use in allowing recursion for
anonymous function
In computer programming, an anonymous function (function literal, lambda abstraction, lambda function, lambda expression or block) is a function definition that is not bound to an identifier. Anonymous functions are often arguments being passed t ...
s, particularly when they form
closures or are used as
callbacks
In computer programming, a callback or callback function is any reference to executable code that is passed as an argument to another piece of code; that code is expected to ''call back'' (execute) the callback function as part of its job. Thi ...
, to avoid having to
bind the name of the function.
Anonymous recursion primarily consists of calling "the current function", which results in
direct recursion
In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursive problems by using functions that call themselves ...
. Anonymous
indirect recursion
In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursion, recursive problems by using function (computer sci ...
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 data structure that stores information about the active subroutines of a computer program. This kind of stack is also known as an execution stack, program stack, control stack, run-time stack, or mach ...
, and this can be chained to produce
mutual recursion. The
self-reference
Self-reference occurs in natural or formal languages when a sentence, idea or formula refers to itself. The reference may be expressed either directly—through some intermediate sentence or formula—or by means of some encoding. In philos ...
of "the current function" is a functional equivalent of the "
this
This may refer to:
* ''This'', the singular proximal demonstrative pronoun
Places
* This, or ''Thinis'', an ancient city in Upper Egypt
* This, Ardennes, a commune in France
People with the surname
* Hervé This, French culinary chemist Art ...
" keyword in
object-oriented programming
Object-oriented programming (OOP) is a programming paradigm based on the concept of " objects", which can contain data and code. The data is in the form of fields (often known as attributes or ''properties''), and the code is in the form of ...
, 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 code style, is a set of rules or guidelines used when writing the source code for a computer program. It is often claimed that following a particular programming style will help programmers read and understand sou ...
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, 5
The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline o ...
map(function(n) );
Rewritten to use a named function expression yields:
, 2, 3, 4, 5
The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline o ...
map(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 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 itse ...
called a ''
combinator
Combinatory logic is a notation to eliminate the need for quantified variables in mathematical logic. It was introduced by Moses Schönfinkel and Haskell Curry, and has more recently been used in computer science as a theoretical model of compu ...
:''
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
Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation t ...
, which only uses functions of a single variable, this can be done via the ''
Y combinator
Y Combinator (YC) is an American technology startup accelerator launched in March 2005. It has been used to launch more than 3,000 companies, including Airbnb, Coinbase, Cruise, DoorDash, Dropbox, Instacart, Quora, PagerDuty, Reddit, Str ...
.'' 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 the evaluation of a function that takes multiple arguments into evaluating a sequence of functions, each with a single argument. For example, currying a function f tha ...
:
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
Combinatory logic is a notation to eliminate the need for quantified variables in mathematical logic. It was introduced by Moses Schönfinkel and Haskell Curry, and has more recently been used in computer science as a theoretical model of compu ...
'' 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 (YC) is an American technology startup accelerator launched in March 2005. It has been used to launch more than 3,000 companies, including Airbnb, Coinbase, Cruise, DoorDash, Dropbox, Instacart, Quora, PagerDuty, Reddit, Str ...
:
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 that is one of the core technologies of the World Wide Web, alongside HTML and CSS. As of 2022, 98% of Website, websites use JavaScript on the Client (computing), client side ...
, 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, 5
The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline o ...
map(function(n) );
Perl
Starting with Perl
Perl is a family of two High-level programming language, high-level, General-purpose programming language, general-purpose, Interpreter (computing), interpreted, dynamic programming languages. "Perl" refers to Perl 5, but from 2000 to 2019 it ...
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/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 R code