無名再帰

無名再帰（むめいさいき、）とは、無名関数において再帰を行うことである。無名関数は名前を持たないため自己を呼び出すために特別の工夫が必要である。無名再帰は、関数定義では関数自身には名前を付けないが、関数の引数には名前を付けて良い、という制約条件で行う再帰。ラムダ計算において関数はそのような制約条件がある。

不動点コンビネータによる方法 

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)))
# 利用方法（5の階乗の計算）
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) { ->(x) { f[->(y) { x[x][y] }] }[->(x) { f[->(y) { x[x][y] }] }] }
# 利用方法（5の階乗の計算）
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)
# 利用方法（5の階乗の計算）
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)
# 利用方法（5の階乗の計算）
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 を ∇　で参照できる。
   {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 ではワードの定義中では、名前を用いて自分自身を参照できないため、RECURSE というワードで自分自身を参照する。

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 から同様に、 というリテラル（厳密には組込み関数）が、実行中のサブルーチン自身へのリファレンスを返し、無名再帰に利用できるようになった。

#!/usr/bin/perl
use feature qw/current_sub say/;

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

R 
R言語 では Recall で関数の自己参照ができる。
sapply(0:5, function(n) {
  if (n == 0) return(1)
  n * Recall(n - 1)
})

参照 

再帰
プログラミング