当前位置: 首页 > 编程笔记 >

JavaScript中匿名函数的递归调用

萧星火
2023-03-14
本文向大家介绍JavaScript中匿名函数的递归调用,包括了JavaScript中匿名函数的递归调用的使用技巧和注意事项,需要的朋友参考一下

不管是什么编程语言,相信稍微写过几行代码的同学,对递归都不会陌生。 以一个简单的阶乘计算为例:

function factorial(n) { 
  if (n <= 1) {
    return 1;
  } else {
    return n * factorial(n-1);
  }
}

我们可以看出,递归就是在函数内部调用对自身的调用。 那么问题来了,我们知道在Javascript中,有一类函数叫做匿名函数,没有名称,怎么调用呢?当然你可以说,可以把匿名函数赋值给一个常量:

const factorial = function(n){ 
   if (n <= 1) {
    return 1;
  } else {
    return n * factorial(n-1);
  }
}

这当然是可以的。但是对于一些像,函数编写时并不知道自己将要赋值给一个明确的变量的情况时,就会遇到麻烦了。如:

(function(f){
  f(10);
})(function(n){
   if (n <= 1) {
    return 1;
  } else {
    return n * factorial(n-1);//太依赖于上下文变量名
  }
})
//Uncaught ReferenceError: factorial is not defined(…)

那么存不存在一种完全不需要这种给予准确函数名(函数引用变量名)的方式呢?

arguments.callee

我们知道在任何一个function内部,都可以访问到一个叫做arguments的变量。

(function(){console.dir(arguments)})(1,2)

屏幕快照 2016-09-18 下午10.53.58

打印出这个arguments变量的细节,可以看出他是Arguments的一个实例,而且从数据结构上来讲,他是一个类数组。他除了类数组的元素成员和length属性外,还有一个callee方法。 那么这个callee方法是做什么的呢?我们来看下MDN

callee 是 arguments 对象的属性。在该函数的函数体内,它可以指向当前正在执行的函数。当函数是匿名函数时,这是很有用的, 比如没有名字的函数表达式 (也被叫做”匿名函数”)。

哈哈,很明显这就是我们想要的。接下来就是:

(function(f){
  console.log(f(10));
})(function(n){
   if (n <= 1) {
    return 1;
  } else {
    return n * arguments.callee(n-1);
  }
})
//output: 3628800

但是还有一个问题,MDN的文档里明确指出

警告:在 ECMAScript 第五版 (ES5) 的 严格模式 中禁止使用 arguments.callee()。

哎呀,原来在ES5的use strict;中不给用啊,那么在ES6中,我们换个ES6的arrow function写写看:

((f) => console.log(f(10)))(
  (n) => n <= 1? 1: arguments.callee(n-1))
//Uncaught ReferenceError: arguments is not defined(…)

有一定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组合子。

// 首先我们定义这样一个可以用作求阶乘的递归函数
const fact = (n) => n<=1?1:n*fact(n-1) 
console.log(fact(5)) //120
// 既然不让这个函数有名字,我们就先给这个递归方法一个叫做self的代号
// 首先是一个接受这个递归函数作为参数的一个高阶函数
const fact_gen = (self) => (n) => n<=1?1:n*self(n-1) 
console.log(fact_gen(fact)(5)) //120
// 我们是将递归方法和参数n,都传入递归方法,得到这样一个函数
const fact1 = (self, n) => n<=1?1:n*self(self, n-1) 
console.log(fact1(fact1, 5)) //120
// 我们将fact1 柯理化,得到fact2
const fact2 = (self) => (n) => n<=1?1:n*self(self)(n-1) 
console.log(fact2(fact2)(5)) //120
// 惊喜的事发生了,如果我们将self(self)看做一个整体
// 作为参数传入一个新的函数: (g)=> n<= 1? 1: n*g(n-1)
const fact3 = (self) => (n) => ((g)=>n <= 1?1:n*g(n-1))(self(self)) 
console.log(fact3(fact3)(5)) //120
// fact3 还有一个问题是这个新抽离出来的函数,是上下文有关的
// 他依赖于上文的n, 所以我们将n作为新的参数
// 重新构造出这么一个函数: (g) => (m) => m<=1?1:m*g(m-1)
const fact4 = (self) => (n) => ((g) => (m) => m<=1?1:m*g(m-1))(self(self))(n) 
console.log(fact4(fact4)(5))
// 很明显fact4中的(g) => (m) => m<=1?1:m*g(m-1) 就是 fact_gen
// 这就很有意思啦,这个fact_gen上下文无关了, 可以作为参数传入了
const weirdFunc = (func_gen) => (self) => (n) => func_gen(self(self))(n) 
console.log(weirdFunc(fact_gen)(weirdFunc(fact_gen))(5)) //120
// 此时我们就得到了一种Y组合子的形式了
const Y_ = (gen) => (f) => (n)=> gen(f(f))(n)
// 构造一个阶乘递归也很easy了
const factorial = Y_(fact_gen) 
console.log(factorial(factorial)(5)) //120
// 但上面这个factorial并不是我们想要的
// 只是一种fact2,fact3,fact4的形式
// 我们肯定希望这个函数的调用是factorial(5)
// 没问题,我们只需要把定义一个 f' = f(f) = (f)=>f(f)
// eg. const factorial = fact2(fact2)
const Y = gen => n => (f=>f(f))(gen)(n) 
console.log(Y(fact2)(5)) //120 
console.log(Y(fact3)(5)) //120 
console.log(Y(fact4)(5)) //120

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

来,我们回忆下,我们最终是不是得到了一个不定点算子,这个算子可以找出一个高阶函数的不动点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递归调用有差不多一个数量级的差异,将不定点函数算出后保存下来,大概会有一倍左右的性能提升。

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,同时也希望多多支持小牛知识库!

 类似资料:
  • 问题内容: 是否可以具有递归和匿名的PHP函数?这是我尝试使其工作,但未传入函数名称。 我还知道这是实现阶乘的一种不好方法,这只是一个例子。 问题答案: 为了使其正常工作,您需要传递$ factorial作为参考

  • 问题内容: 我可以在变量中创建一个递归函数,如下所示: 这样,将输出 。假设我做了以下事情: 将输出 如上。如果我再更改如下: 然后将给出,如预期的那样。 现在给出 它所指的,而不是函数(它本身指向的)。在某些情况下这可能是理想的,但是有没有一种方法可以编写函数以便它调用自身而不是保存它的变量? 也就是说,是否可以 仅 更改线路,以便 在调用时仍能完成所有这些步骤?我试过了,但这给了我错误。 问题

  • php版本: 5.4 我定义了一个这样的函数 输出是 如何在的正文中引用。

  • 本文向大家介绍什么是JavaScript中的自调用匿名函数?,包括了什么是JavaScript中的自调用匿名函数?的使用技巧和注意事项,需要的朋友参考一下 在JavaScript中,用括号括起来的函数称为“立即调用函数表达式”或“自执行函数”。 包装的目的是为了命名空间并控制成员函数的可见性。它将代码包装在函数范围内,并减少了与其他库的冲突。这就是我们所说的立即调用函数表达式(IIFE)或自执行匿

  • 问题内容: 我有一个包含方法的对象。这些方法被放入匿名函数内部的对象中。看起来像这样: (还有很多代码,但这足以显示问题) 现在,在某些情况下,我想停止事件监听器。因此,我试图做一个removeEventListener,但我不知道如何去做。我已经读过其他问题,无法在匿名函数上调用removeEventListener,但是在这种情况下也是如此吗? 我在匿名函数内部创建了一个t方法,因此我认为这是

  • 本文向大家介绍Javascript 实现匿名递归的实例代码,包括了Javascript 实现匿名递归的实例代码的使用技巧和注意事项,需要的朋友参考一下 递归是一种常见的编程技巧,实名递归相信大家都不陌生,但如果想要实现匿名递归呢?比如想要返回一个匿名递归函数,又或者是定义一个匿名递归函数并直接调用它,该怎样去做呢?本文将来探讨一下它的实现。 实名递归 我们还是先从实名递归说起吧,还是用那个最简单的