Anonymous recursion - Revision history

Frap: /* Perl */

2025-04-30T12:49:25Z

Perl

← Previous revision		Revision as of 12:49, 30 April 2025
Line 130:		Line 130:
	Starting with [[Perl]] 5.16, the current subroutine is accessible via the <code>__SUB__</code> token, which returns a reference to the current subroutine, or <code>undef</code> outside a subroutine.<ref>Perldoc, "[http://perldoc.perl.org/feature.html#The-'current_sub'-feature The 'current_sub' feature]", perldoc feature</ref> This allows anonymous recursion, such as in the following implementation of the factorial:		Starting with [[Perl]] 5.16, the current subroutine is accessible via the <code>__SUB__</code> token, which returns a reference to the current subroutine, or <code>undef</code> outside a subroutine.<ref>Perldoc, "[http://perldoc.perl.org/feature.html#The-'current_sub'-feature The 'current_sub' feature]", perldoc feature</ref> This allows anonymous recursion, such as in the following implementation of the factorial:
	<syntaxhighlight lang="perl">		<syntaxhighlight lang="perl">
	#!/usr/bin/perl		#!/usr/bin/env perl
	use feature ":5.16";		use feature ":5.16";

Frap: Add category

2025-02-13T19:24:14Z

Add category

← Previous revision		Revision as of 19:24, 13 February 2025
Line 166:		Line 166:

	[[Category:Recursion]]		[[Category:Recursion]]
			[[Category:Articles with example JavaScript code]]
			[[Category:Articles with example Python (programming language) code]]
	[[Category:Articles with example R code]]		[[Category:Articles with example R code]]

LicenceToCrenellate: Linting fix

2022-12-15T14:54:24Z

Linting fix

← Previous revision		Revision as of 14:54, 15 December 2022
Line 18:		Line 18:
	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 (programming language)\|Go]].<ref>[https://code.google.com/p/go/issues/detail?id=226 Issue 226: It's impossible to recurse a anonymous function in Go without workarounds.]</ref>		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 (programming language)\|Go]].<ref>[https://code.google.com/p/go/issues/detail?id=226 Issue 226: It's impossible to recurse a anonymous function in Go without workarounds.]</ref>

	For example, in JavaScript the factorial function can be defined via anonymous recursion as such:<ref name=olliej>[https://stackoverflow.com/a/235760 answer] by olliej, Oct 25 '08 to "[https://stackoverflow.com/q/103598 Why was the arguments.callee.caller property deprecated in JavaScript?]", ''StackOverflow</ref>		For example, in JavaScript the factorial function can be defined via anonymous recursion as such:<ref name=olliej>[https://stackoverflow.com/a/235760 answer] by olliej, Oct 25 '08 to "[https://stackoverflow.com/q/103598 Why was the arguments.callee.caller property deprecated in JavaScript?]", ''StackOverflow''</ref>
	<syntaxhighlight lang="javascript">		<syntaxhighlight lang="javascript">
	[1, 2, 3, 4, 5].map(function(n) {		[1, 2, 3, 4, 5].map(function(n) {

Frap: /* Alternatives */

2020-10-14T11:58:01Z

Alternatives

← Previous revision		Revision as of 11:58, 14 October 2020
Line 19:		Line 19:

	For example, in JavaScript the factorial function can be defined via anonymous recursion as such:<ref name=olliej>[https://stackoverflow.com/a/235760 answer] by olliej, Oct 25 '08 to "[https://stackoverflow.com/q/103598 Why was the arguments.callee.caller property deprecated in JavaScript?]", ''StackOverflow</ref>		For example, in JavaScript the factorial function can be defined via anonymous recursion as such:<ref name=olliej>[https://stackoverflow.com/a/235760 answer] by olliej, Oct 25 '08 to "[https://stackoverflow.com/q/103598 Why was the arguments.callee.caller property deprecated in JavaScript?]", ''StackOverflow</ref>
	<syntaxhighlight lang=javascript>		<syntaxhighlight lang="javascript">
	[1,2,3,4,5].map(function(n) {		[1, 2, 3, 4, 5].map(function(n) {
	return (!(n>1))? 1 : arguments.callee(n-1)*n;		return (!(n > 1)) ? 1 : arguments.callee(n-1) * n;
	});		});
	</syntaxhighlight>		</syntaxhighlight>
	Rewritten to use a named function expression yields:		Rewritten to use a named function expression yields:
	<syntaxhighlight lang=javascript>		<syntaxhighlight lang="javascript">
	[1,2,3,4,5].map(function factorial(n) {		[1, 2, 3, 4, 5].map(function factorial(n) {
	return (!(n>1))? 1 : factorial(n-1)*n;		return (!(n > 1)) ? 1 : factorial(n-1) * n;
	});		});
	</syntaxhighlight>		</syntaxhighlight>

Line 37:		Line 37:

	This is illustrated below using Python. First, a standard named recursion:		This is illustrated below using Python. First, a standard named recursion:
	<syntaxhighlight lang=python>		<syntaxhighlight lang="python">
	def fact(n):		def fact(n):
	if n == 0:		if n == 0:
Line 44:		Line 44:
	</syntaxhighlight>		</syntaxhighlight>
	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:		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:
	<syntaxhighlight lang=python>		<syntaxhighlight lang="python">
	def fact0(n0):		def fact0(n0):
	if n0 == 0:		if n0 == 0:
Line 53:		Line 53:
	</syntaxhighlight>		</syntaxhighlight>
	We can eliminate the standard recursive function by passing the function argument into the call:		We can eliminate the standard recursive function by passing the function argument into the call:
	<syntaxhighlight lang=python>		<syntaxhighlight lang="python">
	fact1 = lambda f, n1: 1 if n1 == 0 else n1 * f(f, n1 - 1)		fact1 = lambda f, n1: 1 if n1 == 0 else n1 * f(f, n1 - 1)
	fact = lambda n: fact1(fact1, n)		fact = lambda n: fact1(fact1, n)
	</syntaxhighlight>		</syntaxhighlight>
	The second line can be replaced by a generic [[higher-order function]] called a ''[[Combinatory logic\|combinator]]:''		The second line can be replaced by a generic [[higher-order function]] called a ''[[Combinatory logic\|combinator]]:''
	<syntaxhighlight lang=python>		<syntaxhighlight lang="python">
	F = lambda f: (lambda x: f(f, x))		F = lambda f: (lambda x: f(f, x))
	fact1 = lambda f, n1: 1 if n1 == 0 else n1 * f(f, n1 - 1)		fact1 = lambda f, n1: 1 if n1 == 0 else n1 * f(f, n1 - 1)
Line 64:		Line 64:
	</syntaxhighlight>		</syntaxhighlight>
	Written anonymously:<ref>[https://stackoverflow.com/a/8703135/2025416 Hugo Walter's answer] to "[https://stackoverflow.com/q/481692 Can a lambda function call itself recursively in Python?]"</ref>		Written anonymously:<ref>[https://stackoverflow.com/a/8703135/2025416 Hugo Walter's answer] to "[https://stackoverflow.com/q/481692 Can a lambda function call itself recursively in Python?]"</ref>
	<syntaxhighlight lang=python>		<syntaxhighlight lang="python">
	(lambda f: (lambda x: f(f, x))) \		(lambda f: (lambda x: f(f, x))) \
	(lambda g, n1: 1 if n1 == 0 else n1 * g(g, n1 - 1))		(lambda g, n1: 1 if n1 == 0 else n1 * g(g, n1 - 1))
Line 70:		Line 70:

	In the [[lambda calculus]], which only uses functions of a single variable, this can be done via the ''[[Fixed-point combinator\|Y combinator]].'' First make the higher-order function of two variables be a function of a single variable, which directly returns a function, by [[currying]]:		In the [[lambda calculus]], which only uses functions of a single variable, this can be done via the ''[[Fixed-point combinator\|Y combinator]].'' First make the higher-order function of two variables be a function of a single variable, which directly returns a function, by [[currying]]:
	<syntaxhighlight lang=python>		<syntaxhighlight lang="python">
	fact1 = lambda f: (lambda n1: 1 if n1 == 0 else n1 * f(f)(n1 - 1))		fact1 = lambda f: (lambda n1: 1 if n1 == 0 else n1 * f(f)(n1 - 1))
	fact = fact1(fact1)		fact = fact1(fact1)
	</syntaxhighlight>		</syntaxhighlight>
	There are two "applying a higher order function to itself" operations here: <code>f(f)</code> in the first line and <code>fact1(fact1)</code> in the second. Factoring out the second double application into a ''[[Combinatory logic\|combinator]]'' yields:		There are two "applying a higher order function to itself" operations here: <code>f(f)</code> in the first line and <code>fact1(fact1)</code> in the second. Factoring out the second double application into a ''[[Combinatory logic\|combinator]]'' yields:
	<syntaxhighlight lang=python>		<syntaxhighlight lang="python">
	C = lambda x: x(x)		C = lambda x: x(x)
	fact1 = lambda f: (lambda n1: 1 if n1 == 0 else n1 * f(f)(n1 - 1))		fact1 = lambda f: (lambda n1: 1 if n1 == 0 else n1 * f(f)(n1 - 1))
Line 81:		Line 81:
	</syntaxhighlight>		</syntaxhighlight>
	Factoring out the other double application yields:		Factoring out the other double application yields:
	<syntaxhighlight lang=python>		<syntaxhighlight lang="python">
	C = lambda x: x(x)		C = lambda x: x(x)
	D = lambda f: (lambda x: f(lambda v: x(x)(v)))		D = lambda f: (lambda x: f(lambda v: x(x)(v)))
Line 88:		Line 88:
	</syntaxhighlight>		</syntaxhighlight>
	Combining the two combinators into one yields the [[Fixed-point combinator\|Y combinator]]:		Combining the two combinators into one yields the [[Fixed-point combinator\|Y combinator]]:
	<syntaxhighlight lang=python>		<syntaxhighlight lang="python">
	C = lambda x: x(x)		C = lambda x: x(x)
	D = lambda f: (lambda x: f(lambda v: x(x)(v)))		D = lambda f: (lambda x: f(lambda v: x(x)(v)))
Line 96:		Line 96:
	</syntaxhighlight>		</syntaxhighlight>
	Expanding out the Y combinator yields:		Expanding out the Y combinator yields:
	<syntaxhighlight lang=python>		<syntaxhighlight lang="python">
	Y = lambda f: (lambda x: f(lambda v: x(x)(v))) \		Y = lambda f: (lambda x: f(lambda v: x(x)(v))) \
	(lambda x: f(lambda v: x(x)(v)))		(lambda x: f(lambda v: x(x)(v)))
Line 103:		Line 103:
	</syntaxhighlight>		</syntaxhighlight>
	Combining these yields a recursive definition of the factorial in lambda calculus (anonymous functions of a single variable):<ref>[https://stackoverflow.com/a/10144992/2025416 Nux's answer] to "[https://stackoverflow.com/q/481692 Can a lambda function call itself recursively in Python?]"</ref>		Combining these yields a recursive definition of the factorial in lambda calculus (anonymous functions of a single variable):<ref>[https://stackoverflow.com/a/10144992/2025416 Nux's answer] to "[https://stackoverflow.com/q/481692 Can a lambda function call itself recursively in Python?]"</ref>
	<syntaxhighlight lang=python>		<syntaxhighlight lang="python">
	(lambda f: (lambda x: f(lambda v: x(x)(v)))		(lambda f: (lambda x: f(lambda v: x(x)(v)))
	(lambda x: f(lambda v: x(x)(v)))) \		(lambda x: f(lambda v: x(x)(v)))) \

DannyS712 bot: Task 70: Update syntaxhighlight tags - remove use of deprecated tags

2020-05-11T17:23:11Z

Task 70: Update syntaxhighlight tags - remove use of deprecated <source> tags

Show changes

Pbsouthwood: Adding local short description: "Recursion without calling a function by name", overriding Wikidata description "recursion without calling a function by name" (Shortdesc helper)

2020-03-09T16:49:09Z

Adding local short description: "Recursion without calling a function by name", overriding Wikidata description "recursion without calling a function by name" (Shortdesc helper)

← Previous revision		Revision as of 16:49, 9 March 2020
Line 1:		Line 1:
			{{short description\|Recursion without calling a function by name}}
	In [[computer science]], '''anonymous recursion''' is [[Recursion (computer science)\|recursion]] which does not explicitly call a function by name. This can be done either explicitly, by using a [[higher-order function]] – passing in a function as an argument and calling it – or implicitly, via [[reflection (computer programming)\|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 [[computer science]], '''anonymous recursion''' is [[Recursion (computer science)\|recursion]] which does not explicitly call a function by name. This can be done either explicitly, by using a [[higher-order function]] – passing in a function as an argument and calling it – or implicitly, via [[reflection (computer programming)\|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".

Frap: /* Examples */ format code

2019-12-18T14:06:44Z

Examples: format code

← Previous revision		Revision as of 14:06, 18 December 2019
Line 120:		Line 120:
	===JavaScript===		===JavaScript===
	In [[JavaScript]], the current function is accessible via <code>arguments.callee</code>, while the calling function is accessible via <code>arguments.caller</code>. These allow anonymous recursion, such as in this implementation of the factorial:<ref name=olliej />		In [[JavaScript]], the current function is accessible via <code>arguments.callee</code>, while the calling function is accessible via <code>arguments.caller</code>. These allow anonymous recursion, such as in this implementation of the factorial:<ref name=olliej />
	<source lang=javascript>		<source lang="javascript">
	[1,2,3,4,5].map(function(n) {		[1, 2, 3, 4, 5].map(function(n) {
	return (!(n>1))? 1 : arguments.callee(n-1)*n;		return (!(n > 1)) ? 1 : arguments.callee(n - 1) * n;
	});		});
	</source>		</source>

	===Perl===		===Perl===
	Starting with [[Perl]] 5.16, the current subroutine is accessible via the <code>__SUB__</code> token, which returns a reference to the current subroutine, or <code>undef</code> outside a subroutine.<ref>Perldoc, "[http://perldoc.perl.org/feature.html#The-'current_sub'-feature The 'current_sub' feature]", perldoc feature</ref> This allows anonymous recursion, such as in the following implementation of the factorial:		Starting with [[Perl]] 5.16, the current subroutine is accessible via the <code>__SUB__</code> token, which returns a reference to the current subroutine, or <code>undef</code> outside a subroutine.<ref>Perldoc, "[http://perldoc.perl.org/feature.html#The-'current_sub'-feature The 'current_sub' feature]", perldoc feature</ref> This allows anonymous recursion, such as in the following implementation of the factorial:
	<source lang=perl>		<source lang="perl">
	#!/usr/bin/perl		#!/usr/bin/perl
	use feature ":5.16";		use feature ":5.16";

	print sub {		print sub {
	my $x = shift;		my $x = shift;
	$x > 0		$x > 0
	? $x * __SUB__->( $x - 1 )		? $x * __SUB__->( $x - 1 )
	: 1;		: 1;
	}->(5), "\n";		}->(5), "\n";
	</source>		</source>
Line 142:		Line 142:
	=== R ===		=== R ===
	In [[R (programming language)\|R]], the current function can be called using <code>Recall</code>. For example,		In [[R (programming language)\|R]], the current function can be called using <code>Recall</code>. For example,
	<source lang=R>		<source lang="r">
	sapply(0:5, function(n) {		sapply(0:5, function(n) {
	if(n == 0) return(1)		if (n == 0) return(1)
	n * Recall(n - 1)		n * Recall(n - 1)
	})		})
Line 151:		Line 151:

	at ''StackOverflow''</ref> For example, the code below squares a list recursively:		at ''StackOverflow''</ref> For example, the code below squares a list recursively:
	<source lang=R>		<source lang="r">
	(function(x) {		(function(x) {
	if(is.list(x)) {		if (is.list(x)) {
	lapply(x, sys.function(0))		lapply(x, sys.function(0))
	} else {		} else {

InverseHypercube: added Category:Articles with example R code using HotCat

2019-12-02T19:04:50Z

added Category:Articles with example R code using HotCat

← Previous revision		Revision as of 19:04, 2 December 2019
Line 165:		Line 165:

	[[Category:Recursion]]		[[Category:Recursion]]
			[[Category:Articles with example R code]]

A.Brudz: Fix title

2019-10-06T12:24:43Z

Fix title

← Previous revision		Revision as of 12:24, 6 October 2019
Line 109:		Line 109:

	==Examples==		==Examples==
	===~~JavaScript~~===		===APL===
	In [[APL (programming language)\|APL]], the current [[Dfns\|dfn]] is accessible via <code>∇</code>. This allows anonymous recursion, such as in this implementation of the factorial:		In [[APL (programming language)\|APL]], the current [[Dfns\|dfn]] is accessible via <code>∇</code>. This allows anonymous recursion, such as in this implementation of the factorial:
	<source lang=apl>		<source lang=apl>

A.Brudz: Add APL

2019-10-06T12:24:30Z

Add APL

← Previous revision		Revision as of 12:24, 6 October 2019
Line 109:		Line 109:

	==Examples==		==Examples==
			===JavaScript===
			In [[APL (programming language)\|APL]], the current [[Dfns\|dfn]] is accessible via <code>∇</code>. This allows anonymous recursion, such as in this implementation of the factorial:
			<source lang=apl>
			{0=⍵:1 ⋄ ⍵×∇ ⍵-1} 5
			120
			{0=⍵:1 ⋄ ⍵×∇ ⍵-1}¨ ⍳10 ⍝ applied to each element of 0 to 9
			1 1 2 6 24 120 720 5040 40320 362880
			</source>

	===JavaScript===		===JavaScript===