php中factorial函数技巧_10种编程措辞实现Y组合子

1 从递归的阶乘函数开始

先不考虑效率等其他成分，写一个最大略的递归阶乘函数。
此处采取Scheme，你可以选择自己熟习的编程措辞随着我一步一步实现Y-Combinator版的阶乘函数。

(define (factorial n) (if (zero? n) 1 ( n (factorial (- n 1)))))

Scheme中 (define (fn-name)) 是 (define fn-name (lambda)) 的简写，就像JS中，function foo() {} 等价于 var foo = function() {}。
把上面的定义展开成Lambda的定义：

(define factorial (lambda (n) (if (zero? n) 1 ( n (factorial (- n 1))))))

2 绑定函数名

想要递归地调用一个函数，就必须给这个函数取一个名字。
匿名函数想要实现递归，就得取一个临时的名字。
所谓临时，指这个名字只在此函数体内有效，函数实行完成后，这个名字就伴随函数一起消逝。
为办理这个问题，第一篇文章中[1]逼迫规定匿名函数有一个隐蔽的名字this指向自己，这导致this这个变量名被强行占用，并不优雅，因此第二篇文章[2]借鉴Clojure的方法，许可自定义一个名字。

但在Lambda演算中，只有最普通的Lambda，没有赋值语句，如何绑定一个名字呢？答案是利用Lambda的参数列表！

(lambda (factorial) (lambda (n) (if (zero? n) 1 ( n (factorial (- n 1))))))

3 天生阶乘函数的函数

虽然通过参数列表，即利用闭包技能给匿名函数取了一个名字，但此函数并不是我们想要的阶乘函数，而是阶乘函数的元函数（meta-factorial），即天生阶乘函数的函数。
因此须要实行这个元函数，得到想要的阶乘函数：

((lambda (factorial) (lambda (n) (if (zero? n) 1 ( n (factorial (- n 1)))))) xxx)

此时又涌现另一个问题：实参xxx，即形参factorial该取什么值？从定义来看，factorial便是函数自身，既然是“自身”，首先想到的便是复制一份千篇一律的代码：

((lambda (factorial) (lambda (n) (if (zero? n) 1 ( n (factorial (- n 1)))))) (lambda (factorial) (lambda (n) (if (zero? n) 1 ( n (factorial (- n 1)))))))

看起来已经把自己通报给了自己，但立时创造 (factorial (- n 1)) 会失落败，由于此时的 factorial 不是一个阶乘函数，而是一个包含阶乘函数的函数，即要获取包含在内部的函数，因此调用办法要改成 ((meta-factorial meta-factorial) (- n 1)) ：

((lambda (meta-factorial) (lambda (n) (if (zero? n) 1 ( n ((meta-factorial meta-factorial) (- n 1)))))) (lambda (meta-factorial) (lambda (n) (if (zero? n) 1 ( n ((meta-factorial meta-factorial) (- n 1)))))))

把名字改成meta-factorial就能清晰地看出它是阶乘的元函数，而不是阶乘函数本身。

4 去除重复

以上代码已经实现了lambda的自我调用，但个中包含重复的代码，meta-factorial即做函数又做参数，即 (meta meta) ：

((lambda (meta) (meta meta)) (lambda (meta-factorial) (lambda (n) (if (zero? n) 1 ( n ((meta-factorial meta-factorial) (- n 1)))))))

5 提取阶乘函数

由于我们想要的是阶乘函数，以是用factorial取代 (meta-factorial meta-factorial) ，方法同样是利用参数列表命名：

((lambda (meta) (meta meta)) (lambda (meta-factorial) ((lambda (factorial) (lambda (n) (if (zero? n) 1 ( n (factorial (- n 1)))))) (meta-factorial meta-factorial))))

这段代码还不能正常运行，由于Scheme以及其他主流的编程措辞实现都采取“运用序”，即实行函数时先打算参数的值，因此 (meta-factorial meta-factorial) 原来是在求阶乘的过程中才被实行，现在提取出来后实行的韶光被提前，于是陷入无限循环。
办理方法是把它包装在Lambda中（你学到了Lambda的另一个用途：延迟实行）。

((lambda (meta) (meta meta)) (lambda (meta-factorial) ((lambda (factorial) (lambda (n) (if (zero? n) 1 ( n (factorial (- n 1)))))) (lambda args (apply (meta-factorial meta-factorial) args)))))

此时，代码中第4行到第8行正是最初定义的匿名递归阶乘函数，我们终于得到了阶乘函数本身！

6 形成模式

如果把个中的阶乘函数作为一个整体提取出来，那便是得到一种“模式”，即能天生任意匿名递归函数的模式：

((lambda (fn) ((lambda (meta) (meta meta)) (lambda (meta-fn) (fn (lambda args (apply (meta-fn meta-fn) args)))))) (lambda (factorial) (lambda (n) (if (zero? n) 1 ( n (factorial (- n 1)))))))

Lambda演算中称这个模式为Y组合子（Y-Combinator），即：

(define (y-combinator fn) ((lambda (meta) (meta meta)) (lambda (meta-fn) (fn (lambda args (apply (meta-fn meta-fn) args))))))

有了Y组合子，我们就能定义任意的匿名递归函数。
前文中定义的是递归求阶乘，再定义一个递归求斐波那契数：

(y-combinator (lambda (fib) (lambda (n) (if (< n 3) 1 (+ (fib (- n 1)) (fib (- n 2)))))))二 10种实现

下面用10种不同的编程措辞实现Y组合子，以及Y版的递归阶乘函数。
实际开拓中可能不会用上这样的技巧，但这些代码分别展示了这10种措辞的诸多语法特性，能帮助你理解如何在这些措辞中实现以下功能：

这10种编程措辞，有Python、PHP、Perl、Ruby等大家耳熟能详的脚本措辞，估计最让大家惊异的该当是个中有Java！

1 Scheme

我始终以为Scheme版是这么多种实现中最优雅的！
它没有“刻意”的简洁，读起来很自然。

(define (y-combinator f) ((lambda (u) (u u)) (lambda (x) (f (lambda args (apply (x x) args))))))((y-combinator (lambda (factorial) (lambda (n) (if (zero? n) 1 ( n (factorial (- n 1))))))) 10) ; => 3628800

2 Clojure

实在Clojure不须要借助Y-Combinator就能实现匿名递归函数，它的lambda——fn——支持通报一个函数名，为这个临时函数命名。
大概Clojure的fn不应该叫匿名函数，该当叫临时函数更贴切。

同样是Lisp，Clojure版本比Scheme版本更简短，却让我觉得是一种刻意的简洁。
我喜好用fn取代lambda，但用稀奇古怪的符号来缩减代码量会让代码的可读性变差（我最近彷佛变得不太喜好用符号，哈哈）。

(defn y-combinator [f] (#(% %) (fn [x] (f #(apply (x x) %&)))))((y-combinator (fn [factorial] #(if (zero? %) 1 ( % (factorial (dec %)))))) 10)

3 Common Lisp

Common Lisp版和Scheme版实在差不多，只不过Common Lisp属于Lisp-2，即函数命名空间与变量命名空间不同，因此调用匿名函数时须要额外的funcall。
我个人不喜好这个额外的调用，以为它是冗余信息，位置信息已经包含了角色信息，就像命令行的第一个参数永久是命令。

(defun y-combinator (f) ((lambda (u) (funcall u u)) (lambda (x) (funcall f (lambda (&rest args) (apply (funcall x x) args))))))(funcall (y-combinator (lambda (factorial) (lambda (n) (if (zerop n) 1 ( n (funcall factorial (1- n))))))) 10)

4 Ruby

Ruby从Lisp那儿借鉴了许多，包括它的缺陷。
和Common Lisp一样，Ruby中实行一个匿名函数也须要额外的“.call”，或者利用中括号“[]”而不是和普通函数一样的小括号“()”，总之在Ruby中匿名函数与普通函数不一样！
还有繁杂的符号也影响我在Ruby中利用匿名函数的心情，因此我会把Ruby看作语法更灵巧、更简洁的Java，而不会考虑写函数式风格的代码。

def y_combinator(&f) lambda {|&u| u[&u]}.call do |&x| f[&lambda {|a| x[&x][a]}] endendy_combinator do |&factorial| lambda {|n| n.zero? ? 1: nfactorial[n-1]}end[10]

5 Python

Python中匿名函数的利用办法与普通函数一样，就这段代码而言，Python之于Ruby就像Scheme之于Common Lisp。
但Python对Lambda的支持切实其实弱爆了，函数体只许可有一条语句！
我决定我的工具箱中用Python取代C措辞，虽然Python对匿名函数的支持只比C措辞好一点点。

def y_combinator(f): return (lambda u: u(u))(lambda x: f(lambda args: x(x)(args)))y_combinator(lambda factorial: lambda n: 1 if n < 2 else n factorial(n-1))(10)

6 Perl

我个人对Perl函数不能声明参数的抱怨愈甚于繁杂的符号！

sub y_combinator { my $f = shift; sub { $_[0]->($_[0]); }->(sub { my $x = shift; $f->(sub { $x->($x)->(@_); }); });}print y_combinator(sub { my $factorial = shift; sub { $_[0] < 2? 1: $_[0] $factorial->($_[0] - 1); };})->(10);

假设Perl能像其他措辞一样声明参数列表，代码会更简洁直不雅观：

sub y_combinator($f) { sub($u) { $u->($u); }->(sub($x) { $f->(sub { $x->($x)->(@_); }); });}print y_combinator(sub($factorial) { sub($n) { $n < 2? 1: $n $factorial->($n - 1); };})->(10);

7 JavaScript

JavaScript无疑是脚本措辞中最盛行的！
但冗长的function、return等关键字总是刺痛我的神经：

var y_combinator = function(fn) { return (function(u) { return u(u); })(function(x) { return fn(function() { return x(x).apply(null, arguments); }); });};y_combinator(function(factorial) { return function(n) { return n <= 1? 1: n factorial(n - 1); };})(10);

ES6供应了 => 语法，可以更加简洁：

const y_combinator = fn => (u => u(u))(x => fn((...args) => x(x)(...args)));y_combinator(factorial => n => n <= 1? 1: n factorial(n - 1))(10);

8 Lua

Lua和JavaScript有相同的毛病，最让我意外的是它没有三元运算符！
不过没有利用花括号让代码看起来清爽不少~

function y_combinator(f) return (function(u) return u(u) end)(function(x) return f(function(...) return x(x)(...) end) end)endprint(y_combinator(function(factorial) return function(n) return n < 2 and 1 or n factorial(n-1) endend)(10))

把稳：Lua版本为5.2。
5.1的语法不同，需将 x(x)(...) 换成 x(x)(unpack(arg))。

9 PHP

PHP也是JavaScript的难兄难弟，function、return……

此外，PHP版本是脚本措辞中符号（$、_、()、{}）用的最多的！
是的，比Perl还多。

function y_combinator($f) { return call_user_func(function($u) { return $u($u); }, function($x) use ($f) { return $f(function() use ($x) { return call_user_func_array($x($x), func_get_args()); }); });}echo call_user_func(y_combinator(function($factorial) { return function($n) use ($factorial) { return ($n < 2)? 1: ($n $factorial($n-1)); };}), 10);

10 Java

末了，Java登场。
我说的不是Java 8，即不是用Lambda表达式，而是匿名类！
匿名函数的意义是把代码块作为参数通报，这正是匿名类所做得事情。

干系链接

[1]http://zzp.me/2011-08-05/recursive-lambda/[2]http://zzp.me/2012-08-04/clojure-style-lambda-in-common-lisp/

作者 | 技师

本文为阿里云原创内容，未经许可不得转载。