Anonymous recursion

In computer science, anonymous recursion is recursion which does not explicitly call a function by name, but rather implicitly calls a function depending on the current context, especially "the current function" or sometimes "the calling function of the current function". This is supported in some programming languages via keywords (or other constructions) that allow one to refer to the current context, and more abstractly can be produced via fixed-point combinators.

Use

Anonymous recursion is primarily of use in allowing recursion for anonymous functions, 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, and this can be chained to produce mutual recursion. The self-reference of "the current function" is a functional equivalent of the "this" keyword in object-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 of programming style this is generally not done.

Alternatives

If anonymous recursion is not possible or not desired, one must instead 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.

For example, in JavaScript the factorial function can be defined via anonymous recursion as such:

[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(function factorial(n) {
     return (!(n>1))? 1 : factorial(n-1)*n;
 });

Other uses

"Anonymous recursion" may also refer to the use of fixed-point combinators. This is because in programming languages that support anonymous functions, fixed-point combinators can be used to produce anonymous recursion.

Examples

JavaScript

In JavaScript, 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:

[1,2,3,4,5].map(function(n) {
     return (!(n>1))? 1 : arguments.callee(n-1)*n;
 });

Perl

Starting with Perl 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:

use feature ":5.16";

sub {
  my $x = shift;
  $x == 0 ? 1 : $x * __SUB__->( $x - 1 );
}