不管是什么编程语言,相信稍微写过几行代码的同学,对递归都不会陌生。 以一个简单的阶乘计算为例:
我们可以看出,递归就是在函数内部调用对自身的调用。 那么问题来了,我们知道在Javascript中,有一类函数叫做匿名函数,没有名称,怎么调用呢?当然你可以说,可以把匿名函数赋值给一个常量:
这当然是可以的。但是对于一些像,函数编写时并不知道自己将要赋值给一个明确的变量的情况时,就会遇到麻烦了。如:
那么存不存在一种完全不需要这种给予准确函数名(函数引用变量名)的方式呢?
arguments.callee
我们知道在任何一个function内部,都可以访问到一个叫做arguments的变量。
(function(){console.dir(arguments)})(1,2)
屏幕快照 2016-09-18 下午10.53.58
打印出这个arguments变量的细节,可以看出他是Arguments的一个实例,而且从数据结构上来讲,他是一个类数组。他除了类数组的元素成员和length属性外,还有一个callee方法。 那么这个callee方法是做什么的呢?我们来看下MDN
callee 是 arguments 对象的属性。在该函数的函数体内,它可以指向当前正在执行的函数。当函数是匿名函数时,这是很有用的, 比如没有名字的函数表达式 (也被叫做”匿名函数”)。
哈哈,很明显这就是我们想要的。接下来就是:
但是还有一个问题,MDN的文档里明确指出
警告:在 ECMAScript 第五版 (ES5) 的 严格模式 中禁止使用 arguments.callee()。
哎呀,原来在ES5的use strict;中不给用啊,那么在ES6中,我们换个ES6的arrow function写写看:
有一定ES6基础的同学,估计老早就想说了,箭头函数就是个简写形式的函数表达式,并且它拥有词法作用域的this值(即不会新产生自己作用域下的this,arguments,super 和 new.target等对象),且都是匿名的。
那怎么办呢?嘿嘿,我们需要借助一点FP的思想了。
Y组合子
关于Y Combinator的文章可谓数不胜数,这个由师从希尔伯特的著名逻辑学家Haskell B.Curry(Haskell语言就是以他命名的,而函数式编程语言里面的Curry手法也是以他命名)“发明”出来的组合算子(Haskell是研究组合逻辑(combinatory logic)的)仿佛有种神奇的魔力,它能够算出给定lambda表达式(函数)的不动点。从而使得递归成为可能。
这里需要告知一个概念
不动点组合子
:不动点组合子(英语:Fixed-point combinator,或不动点算子)是计算其他函数的一个不动点的高阶函数。
函数f的不动点是一个值x使得f(x) = x。例如,0和1是函数 f(x) = x^2 的不动点,因为 0^2 = 0而 1^2 = 1。鉴于一阶函数(在简单值比如整数上的函数)的不动点是个一阶值,高阶函数f的不动点是另一个函数g使得f(g) = g。那么,不动点算子是任何函数fix使得对于任何函数f都有
f(fix(f)) = fix(f). 不动点组合子允许定义匿名的递归函数。它们可以用非递归的lambda抽象来定义.
在无类型lambda演算中众所周知的(可能是最简单的)不动点组合子叫做Y组合子。
接下来,我们通过一定的演算推到下这个Y组合子。
推导到这里,是不是已经感觉到脊背嗖凉了一下,反正笔者我第一次接触在康托尔、哥德尔、图灵——永恒的金色对角线这篇文章里接触到的时候,整个人瞬间被这种以数学语言去表示程序的方式所折服。
来,我们回忆下,我们最终是不是得到了一个不定点算子,这个算子可以找出一个高阶函数的不动点f(Y(f)) = Y(f)。 将一个函数传入一个算子(函数),得到一个跟自己功能一样,但又并不是自己的函数,这个说法有些拗口,但又味道十足。
好了,我们回到最初的问题,怎么完成匿名函数的递归呢?有了Y组合子就很简单了:
曾经看到过一些说法是”最让人沮丧是,当你推导出它(Y组合子)后,完全没法儿通过只看它一眼就说出它到底是想干嘛”,而我恰恰认为这就是函数式编程的魅力,也是数学的魅力所在,精简优雅的公式,背后隐藏着复杂有趣的推导过程。
总结
务实点儿讲,匿名函数的递归调用,在日常的js开发中,用到的真的很少。把这个问题拿出来讲,主要是想引出对arguments的一些讲解和对Y组合子这个概念的一个普及。
但既然讲都讲了,我们真的用到的话,该怎么选择呢?来,我们喜闻乐见的benchmark下: 分别测试:
环境:Macbook pro(2.5 GHz Intel Core i7),node-5.0.0(V8:4.6.85.28) 结果:
可见Y和callee的性能相差不多,因为需要临时构建函数,所以跟直接的fact递归调用有差不多一个数量级的差异,将不定点函数算出后保存下来,大概会有一倍左右的性能提升。