無名再帰

無名再帰（むめいさいき、）とは、無名関数において再帰を行うことである。無名関数は名前を持たないため自己を呼び出すために特別の工夫が必要である。無名再帰は、関数定義では関数自身には名前を付けないが、関数の引数には名前を付けて良い、という制約条件で行う再帰。ラムダ計算において関数はそのような制約条件がある。
不動点コンビネータによる方法.
Haskell では以下のように書く。fix が不動点コンビネータ。ラムダ式で引数 f を余分に持っておき、f を自分自身として参照するように記述する。すると、無名再帰となる。
fix (\f n -> if n == 0 then 1 else n * f(n - 1)) 5 == 120
不動点コンビネータを名前付き関数の再帰を使わずに実装する方法.
値呼びYコンビネータのZコンビネータ（下記関数Z）を使用して以下のようにも書ける。名前付き関数 Z の実装において内部から Z を再帰呼び出していない。
Python.
Z = lambda f: (lambda x: f(lambda *y: x(x)(*y)))(lambda x: f(lambda *y: x(x)(*y)))
Z(lambda f: lambda n: 1 if n == 0 else n * f(n - 1))(5)
不動点コンビネータは Python の代入式を使った と同様である。
JavaScript (ECMAScript 2015).
Z = f => (x => f(y => x(x)(y)))(x => f(y => x(x)(y)))
// 利用方法（5の階乗の計算）
Z(f => n => n == 0 ? 1 : n * f(n - 1))(5)
Ruby.
Z[->(f) { ->(n) { n == 0 ? 1 : n * f[n - 1] } }][5]
TypeScript.
Zコンビネータに型をふるには再帰型が必要である。下記の type X が再帰型である。
function Z<A, B>(f: (_: (_: A) => B) => (_: A) => B) {
 type X = (_: X) => (_: A) => B;
 return ((x: X) => f((y: A) => x(x)(y)))((x: X) => f((y: A) => x(x)(y)));
// 利用方法（5の階乗の計算）
Z<number, number>(f => n => n === 0 ? 1 : n * f(n - 1))(5);
Java.
Java で再帰型を利用するには名前付きクラスやインターフェースを使用する必要がある。型 X を表現するのに名前付きインターフェースを使用する。
import java.util.function.Function;
interface X<A, B> {
 Function<A, B> apply(X<A, B> x);
static <A, B> Function<A, B> Z(Function<Function<A, B>, Function<A, B» f) {
 return ((X<A, B>) (x -> f.apply(y -> x.apply(x).apply(y)))).apply(x -> f.apply(y -> x.apply(x).apply(y)));
// 利用方法（5の階乗の計算）
Z((Function<Integer, Integer> f) -> (Integer n) -> n == 0 ? 1 : n * f.apply(n - 1)).apply(5);
不動点コンビネータを名前付き関数の再帰を使って実装する方法.
不動点コンビネータの fix は無名関数だけで実装すると複雑だが、名前付き関数の再帰を使うならば簡単に実装できる。再帰回数が多いとスタックオーバーフローすることがあるが、その際はすれば良い。
Python.
カリー化あり。
def fix(f):
 return lambda *x: f(fix(f))(*x)
fix(lambda f: lambda n: 1 if n == 0 else n * f(n - 1))(5)
カリー化なし。
def fix(f, *x):
 return f(lambda *y: fix(f, *y), *x)
fix(lambda f, n: 1 if n == 0 else n * f(n - 1), 5)
Scala.
複数パラメータリスト（カリー化）を使用。
def fix[A, B](f: (A => B) => A => B)(a: A): B = f(fix(f))(a)
// 利用方法（5の階乗の計算）
fix((f: Int => Int) => (n: Int) => if (n == 0) 1 else n * f(n - 1))(5)
それをトランポリン化。
import scala.util.control.TailCalls._
def fix[A, B](f: (A => TailRec[B]) => A => TailRec[B])(a: A): TailRec[B] = f(a2 => tailcall(fix(f)(a2)))(a)
// 利用方法（0～100000の整数の和）
fix((f: Int => TailRec[Long]) => (n: Int) => if (n == 0) done(0L) else f(n - 1).map(s => s + n))(100000).result
関数の自己参照をサポートしている言語による方法.
APL.
APL, 言語では実行中の dfn を codice_1　で参照できる。
 {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
Forth.
Forth ではワードの定義中では、名前を用いて自分自身を参照できないため、codice_2 というワードで自分自身を参照する。
JavaScript.
JavaScript では以下のように書ける。arguments.callee で自分自身を参照する。なお、ECMAScript 5 以降の strict mode では arguments.callee は使用できない。
(function(n) { return n == 0 ? 1 : n * arguments.callee(n - 1) })(5) == 120
Perl.
Perl でも v5.16 から同様に、codice_3 というリテラル（厳密には組込み関数）が、実行中のサブルーチン自身へのリファレンスを返し、無名再帰に利用できるようになった。
use feature qw/current_sub say/;
say sub {
 my $x = shift;
 $x > 0
 ? $x * __SUB__->( $x - 1 )
 : 1;
}->(5);
R.
R言語 では codice_4 で関数の自己参照ができる。
sapply(0:5, function(n) {
 if (n == 0) return(1)
 n * Recall(n - 1)