Incomputer science,anonymous recursion isrecursion which does not explicitly call a function by name. This can be done either explicitly, by using ahigher-order function – passing in a function as an argument and calling it – or implicitly, viareflection 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 inJavaScript, 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 thelambda calculus, which has anonymous unary functions, but is able to compute any recursive function. This anonymous recursion can be produced generically viafixed-point combinators.
Anonymous recursion is primarily of use in allowing recursion foranonymous functions, particularly when they formclosures or are used ascallbacks, to avoid having tobind the name of the function.
Anonymous recursion primarily consists of calling "the current function", which results indirect recursion. Anonymousindirect recursion is possible, such as by calling "the caller (the previous function)", or, more rarely, by going further up thecall stack, and this can be chained to producemutual recursion. Theself-reference of "the current function" is a functional equivalent of the "this" keyword inobject-oriented programming, 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 ofprogramming style this is generally not done.
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 includeGo.[1]
For example, in JavaScript the factorial function can be defined via anonymous recursion as such:[2]
[1,2,3,4,5].map(function(n){return(!(n>1))?1:arguments.callee(n-1)*n;});
Rewritten to use a named function expression yields:
[1,2,3,4,5].map(functionfactorial(n){return(!(n>1))?1:factorial(n-1)*n;});
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 functionitself allows anonymous recursion within the actual recursive function. This can be done purely anonymously by applying afixed-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.[3][4]
This is illustrated below usingPython. First, a standard named recursion:
deffact(n):ifn==0:return1returnn*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:
deffact0(n0):ifn0==0:return1returnn0*fact0(n0-1)fact1=lambdaf,n1:1ifn1==0elsen1*f(n1-1)fact=lambdan:fact1(fact0,n)
We can eliminate the standard recursive function by passing the function argument into the call:
fact1=lambdaf,n1:1ifn1==0elsen1*f(f,n1-1)fact=lambdan:fact1(fact1,n)
The second line can be replaced by a generichigher-order function called acombinator:
F=lambdaf:(lambdax:f(f,x))fact1=lambdaf,n1:1ifn1==0elsen1*f(f,n1-1)fact=F(fact1)
Written anonymously:[5]
(lambdaf:(lambdax:f(f,x))) \(lambdag,n1:1ifn1==0elsen1*g(g,n1-1))
In thelambda calculus, which only uses functions of a single variable, this can be done via theY combinator. First make the higher-order function of two variables be a function of a single variable, which directly returns a function, bycurrying:
fact1=lambdaf:(lambdan1:1ifn1==0elsen1*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 andfact1(fact1) in the second. Factoring out the second double application into acombinator yields:
C=lambdax:x(x)fact1=lambdaf:(lambdan1:1ifn1==0elsen1*f(f)(n1-1))fact=C(fact1)
Factoring out the other double application yields:
C=lambdax:x(x)D=lambdaf:(lambdax:f(lambdav:x(x)(v)))fact1=lambdag:(lambdan1:1ifn1==0elsen1*g(n1-1))fact=C(D(fact1))
Combining the two combinators into one yields theY combinator:
C=lambdax:x(x)D=lambdaf:(lambdax:f(lambdav:x(x)(v)))Y=lambday:C(D(y))fact1=lambdag:(lambdan1:1ifn1==0elsen1*g(n1-1))fact=Y(fact1)
Expanding out the Y combinator yields:
Y=lambdaf:(lambdax:f(lambdav:x(x)(v))) \(lambdax:f(lambdav:x(x)(v)))fact1=lambdag:(lambdan1:1ifn1==0elsen1*g(n1-1))fact=Y(fact1)
Combining these yields arecursive definition of the factorial in lambda calculus (anonymous functions of a single variable):[6]
(lambdaf:(lambdax:f(lambdav:x(x)(v)))(lambdax:f(lambdav:x(x)(v)))) \(lambdag:(lambdan1:1ifn1==0elsen1*g(n1-1)))
InAPL, the currentdfn is accessible via∇. This allows anonymous recursion, such as in this implementation of the factorial:
{0=⍵:1⋄⍵×∇⍵-1}5120{0=⍵:1⋄⍵×∇⍵-1}¨⍳10⍝ applied to each element of 0 to 9112624120720504040320362880
InJavaScript, the current function is accessible viaarguments.callee, while the calling function is accessible viaarguments.caller. These allow anonymous recursion, such as in this implementation of the factorial:[2]
[1,2,3,4,5].map(function(n){return(!(n>1))?1:arguments.callee(n-1)*n;});
Starting withPerl 5.16, the current subroutine is accessible via the__SUB__ token, which returns a reference to the current subroutine, orundef outside a subroutine.[7] This allows anonymous recursion, such as in the following implementation of the factorial:
#!/usr/bin/env perlusefeature":5.16";printsub{my$x=shift;$x>0?$x*__SUB__->($x-1):1;}->(5),"\n";
InR, the current function can be called usingRecall. For example,
sapply(0:5,function(n){if(n==0)return(1)n*Recall(n-1)})
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.[8] For example, the code below squares a list recursively:
(function(x){if(is.list(x)){lapply(x,sys.function(0))}else{x^2}})(list(list(1,2,3),list(4,5)))