無名再帰

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

無名再帰(むめいさいき、: anonymous recursion, nameless recursion)とは、無名関数において再帰を行うことである。無名関数は名前を持たないため自己を呼び出すために特別の工夫が必要である。

不動点コンビネータによる方法[編集]

Haskell では以下のように書く。fix が不動点コンビネータラムダ式で引数 rec を余分持っておき、rec を自分自身として参照するように記述する。すると、無名再帰となる。

fix (\rec n -> if n == 0 then 1 else n * rec (n - 1)) 5 == 120

JavaScriptにおける方法[編集]

JavaScript では以下のように書ける[1]。arguments.callee で自分自身を参照する。なお、ECMAScript 5 の strict mode では arguments.callee は使用できない。

(function(n) { return n == 0 ? 1 : n * arguments.callee(n - 1); })(5) == 120

なお、Zコンビネータ(下記関数Z)を使用し、以下のようにも書ける[2]。arguments.callee は使用していない。この手法はクロージャを使える他のプログラミング言語でも利用可能。

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

Forthにおける方法[編集]

Forth ではワードの定義中では、名前を用いて自分自身を参照できないため、RECURSE というワードで自分自身を参照する。

参照[編集]