Pythonで階乗を求める(Yコンビネータ編)
Q: 「Pythonで階乗を求める(これはひどい)」はYコンビネータ？
A: いいえ。
再帰呼び出しは普通、以下のように関数が自分自身の名前を使って自分自身を呼び出します。
>>> f = lambda n: n and n * f(n - 1) or 1 >>> f(5) 120
ここで、名前をつけずに、関数自体にも手を加えずに、再帰呼び出しを実現するための手段がYコンビネータです。再帰呼び出しを実現するだけならばYコンビネータは必須ではありません。 前回のコードはYコンビネータを使わずに再帰呼び出しをしています。具体的には、元の関数をnだけを受け取るのではなく、自分自身も引数fに受け取るようにし、また再帰呼び出しでfを呼び出す際にも引数にfを渡してやるようにしています。
Yコンビネータ版は以下。
>>> Y = lambda f:((lambda g: f(lambda x: g(g)(x))) (lambda g: f(lambda x: g(g)(x)))) >>> lambda f: lambda n: n and n * f(n - 1) or 1 <function <lambda> at 0x011DF9B0> >>> Y(_) <function <lambda> at 0x011EB770> >>> _(6) 720 >>> (lambda f:((lambda g: f(lambda x: g(g)(x)))(lambda g: f(lambda x: g(g)(x))))) (lambda f: lambda n: n and n * f(n - 1) or 1)(6) 720「lambda n: n and n * f(n - 1) or 1」がそのまま手を加えられずに使われている(lambda f:～で囲われているだけ)というところがポイントです。前回の「lambda f,x:x and f(f,x-1)*x or 1」は引数を追加してしまっています。
