無名再帰

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

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

詳細は「不動点コンビネータ#不動点コンビネータによる再帰の実現」を参照

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 の代入式を使った (f := lambda n: 1 if n == 0 else n * f(n - 1))(5) と同様である。

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

名前付きラムダ式

多くのプログラミング言語ではラムダ式には名前が付けられないが、名前付きラムダ式を作れたり、変数に代入すれば再帰できるプログラミング言語もある。変数に代入する方法は、そのプログラミング言語が外の変数を参照で束縛することが必要であり、値で束縛すると初期化前なので再帰ができない。

Clojure

ラムダ式に名前が付けられる。

((fn f [n] (if (== n 0) 1 (* n (f (- n 1))))) 5)

なお、不動点コンビネータで実現できるという指摘はあったものの、1960年の最初のバージョンの LISP I では (LABEL 名前 ラムダ式) という構文で再帰可能な名前付きラムダ式が作成できた。

ECMAScript

アロー関数は名前を付けられないが、ECMAScript 3 以降の function は再帰できるように名前を付けられる。

(function f(n) { return n == 0 ? 1 : n * f(n - 1); })(5);

アロー関数の場合は変数に代入すれば再帰が可能。

(f = n => n == 0 ? 1 : n * f(n - 1))(5)

Python

Python 3.8 で導入された代入式を使用すれば再帰が可能。

(f := lambda n: 1 if n == 0 else n * f(n - 1))(5)

Ruby

変数に代入する事でラムダ式も再帰が可能。

(f = -> (n) { n.zero? ? 1 : n * f.(n - 1) }).(5)

C++

外のローカル変数 f の参照を [&f] で束縛することができるので、これを使用して再帰ができる。[f] だと初期化前なので使用することができなく、参照で束縛することで f にラムダ式を代入後の値を使用できる。

#include <functional>
std::function<int(int)> f = [&f](int n) -> int { return (n == 0) ? 1 : n * f(n - 1); };

C#

C++ と似た手法であるが、C# の場合は、変数宣言を分離すると f の参照を束縛できる。これを1行で書くとコンパイルエラーになる。

Func<int, int> f = null!; // null免除演算子で警告を抑止
(f = n => n == 0 ? 1 : n * f(n - 1))(5);

Kotlin

C# と同じく変数宣言を分離し、lateinit を付けることで f の参照を束縛できる。

lateinit var f: (Int) -> Int
f = { n -> if (n == 0) 1 else n * f(n - 1) }

Java

C++ や C# とは異なり Java は外のローカル変数を参照で束縛することができないので、配列を導入すると参照可能になる。

import java.util.function.Function;
Function<Integer, Integer>[] ary = new Function[1];
Function<Integer, Integer> f = ary[0] = n -> n == 0 ? 1 : n * ary[0].apply(n - 1);

フィールドの場合は、this.f とするとコンパイルが可能。this. を付けないと「初期化子内の自己参照」のエラーが出る。static フィールドの場合も Foo.f とする必要がある。

import java.util.function.Function;
class Foo {
    Function<Integer, Integer> f = n -> n == 0 ? 1 : n * this.f.apply(n - 1);
}

関数の自己参照をサポートしている言語による方法

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

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

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

R

R言語 では Recall で関数の自己参照ができる。

sapply(0:5, function(n) {
  if (n == 0) return(1)
  n * Recall(n - 1)
})