JavaScript中匿名函数的递归调用(2)

推导到这里,是不是已经感觉到脊背嗖凉了一下,反正笔者我第一次接触在康托尔、哥德尔、图灵——永恒的金色对角线这篇文章里接触到的时候,整个人瞬间被这种以数学语言去表示程序的方式所折服。

来,我们回忆下,我们最终是不是得到了一个不定点算子,这个算子可以找出一个高阶函数的不动点f(Y(f)) = Y(f)。 将一个函数传入一个算子(函数),得到一个跟自己功能一样,但又并不是自己的函数,这个说法有些拗口,但又味道十足。

好了,我们回到最初的问题,怎么完成匿名函数的递归呢?有了Y组合子就很简单了:

(f => f(f)) (fact => n => n <= 1 ? 1 : n * fact(fact)(n - 1)) (5) // 120

曾经看到过一些说法是”最让人沮丧是,当你推导出它(Y组合子)后,完全没法儿通过只看它一眼就说出它到底是想干嘛”,而我恰恰认为这就是函数式编程的魅力,也是数学的魅力所在,精简优雅的公式,背后隐藏着复杂有趣的推导过程。

总结

务实点儿讲,匿名函数的递归调用,在日常的js开发中,用到的真的很少。把这个问题拿出来讲,主要是想引出对arguments的一些讲解和对Y组合子这个概念的一个普及。

但既然讲都讲了,我们真的用到的话,该怎么选择呢?来,我们喜闻乐见的benchmark下: 分别测试:

// fact fact(10) // Y (f => f(f))(fact => n => n <= 1 ? 1 : n * fact(fact)(n - 1))(10) // Y' const fix = (f) => f(f) const ygen = fix(fact2) ygen(10) // callee (function(n) {n<=1?1:n*arguments.callee(n-1)})(10)

环境:Macbook pro(2.5 GHz Intel Core i7), node-5.0.0(V8:4.6.85.28) 结果:

fact x 18,604,101 ops/sec ±2.22% (88 runs sampled) Y x 2,799,791 ops/sec ±1.03% (87 runs sampled) Y' x 3,678,654 ops/sec ±1.57% (77 runs sampled) callee x 2,632,864 ops/sec ±0.99% (81 runs sampled)

可见Y和callee的性能相差不多,因为需要临时构建函数,所以跟直接的fact递归调用有差不多一个数量级的差异,将不定点函数算出后保存下来,大概会有一倍左右的性能提升。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wwdyww.html