ホームページ >ウェブフロントエンド >jsチュートリアル >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(…)
それでは、正確な関数名 (関数参照変数名) をまったく与える必要がない方法はあるのでしょうか?
どの function
内でも、arguments
という変数にアクセスできることがわかっています。 function
内部,都可以访问到一个叫做arguments
的变量。
(function(){console.dir(arguments)})(1,2)
打印出这个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 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)
/*求不动点*/ (f => f(f)) /*以不动点为参数的递归函数*/ (fact => n => n <= 1 ? 1 : n * fact(fact)(n - 1)) /*递归函数参数*/ (5) // 120この
arguments
変数の詳細を出力すると、これが Arguments
のインスタンスであり、データ構造の観点からは配列に似ていることがわかります。配列のような要素メンバーと length
属性に加えて、callee
メソッドもあります。 では、この callee
メソッドは何をするのでしょうか? MDN を見てみましょう🎜🎜🎜ははは、明らかにそれが私たちが望んでいることです。次のステップは次のとおりです: 🎜callee
はarguments
オブジェクトの属性です。関数の本体内で、現在実行中の関数を指すことができます。これは、名前のない関数式 (「匿名関数」とも呼ばれます) など、関数が匿名である場合に便利です。 🎜
// 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)🎜しかし、MDN ドキュメントには、🎜
🎜Warning
: ECMAScript 第 5 版の厳密モードでは argument.callee の使用が禁止されていると明確に記載されています。 (ES5) ()。 🎜
🎜ああ、ES5 の use strict;
では使用されていないことがわかりました。そこで、ES6 では、ES6 の arrow 関数
に変更して書きましょう。 🎜rrreee🎜 ES6 の基礎を持っている学生ならずっと前から言いたかったかもしれません。 arrow 関数は省略表現の関数式であり、字句スコープの this
値を持ちます。新規ではありません) this
、arguments
、super
、および new.target
オブジェクトを独自に生成します。範囲)、それらはすべて匿名です。 🎜🎜どうすればいいですか?ふふ、ちょっとFPの考え方が必要ですね。 🎜Y コンビネーター
に関する記事は無数にあります。これは、ヒルベルトの下で学んだ有名な論理学者、ハスケル B. カリーによって書かれました (ハスケル言語は彼の名前にちなんで命名されました)。 )彼にちなんで名付けられ、関数型プログラミング言語のカリー手法も彼の名前にちなんで名付けられました)「発明された」(ハスケルは組み合わせ論理を研究している)組み合わせ演算子には魔法の力があるようで、与えられたラムダを計算することができます。式(関数)の。これにより再帰が可能になります。 🎜🎜ここで、固定小数点コンビネータ
という概念についてお知らせする必要があります: 🎜🎜固定小数点コンビネータ(英語:fixed-point combinator、またはfixed-point operandor)は計算に使用されます。その他の関数 固定小数点の高階関数。 🎜🎜関数 f の不動点は、🎜型なしラムダ計算におけるよく知られた (おそらく最も単純な) 固定小数点コンビネータは、Y コンビネータと呼ばれます。 🎜🎜次に、特定の計算を通じてこの Y の組み合わせを導き出します。 🎜rrreee🎜 ここで推測すると、すでに背筋が寒くなるのを感じます。とにかく、これがこの記事の永遠の黄金の対角線であるカントール、ゲーデル、チューリングとの最初の接触です。プログラムを数学的言語で表現するこの方法に感銘を受けました。 🎜🎜さあ、高階関数f(x) = x
となる値 x です。たとえば、0^2 = 0 および 1^2 = 1 であるため、0 と 1 は関数 f(x) = x^2 の固定点です。 1 次関数 (整数などの単純な値に関する関数) の不動点は 1 次の値ですが、高次関数 f の不動点は、f( g) = g
。次に、固定小数点演算子は、任意の関数 f に対して、 🎜🎜f(fix(f)) = fix(f)
となるような関数 fix です。固定小数点コンビネータは、匿名再帰関数の定義を可能にします。これらは、非再帰ラムダ抽象化を使用して定義できます。🎜
f(Y(f)) = Y(f)の不動点を見つけることができる不定点演算子を最終的に得たかどうかを思い出してみましょう。 関数を演算子 (関数) に渡し、それ自体と同じ関数を持つ、独自のものではない関数を取得します。このステートメントは少しぎこちないですが、味わい深いものです。 🎜🎜 さて、元の質問に戻りましょう。匿名関数の再帰を完了するにはどうすればよいでしょうか? Yの組み合わせでとても簡単です: 🎜<pre class="brush:js;toolbar:false;">/*求不动点*/
(f => f(f))
/*以不动点为参数的递归函数*/
(fact => n => n <= 1 ? 1 : n * fact(fact)(n - 1))
/*递归函数参数*/
(5)
// 120</pre><p>曾经看到过一些说法是”最让人沮丧是,当你推导出它(Y组合子)后,完全没法儿通过只看它一眼就说出它到底是想干嘛”,而我恰恰认为这就是函数式编程的魅力,也是数学的魅力所在,精简优雅的公式,背后隐藏着复杂有趣的推导过程。</p>
<p><img src="https://img.php.cn/upload/article/000/000/194/5f7a5e085c1afe1a6078353e02b1f01c-1.jpg" alt=""></p>
<h2>总结</h2>
<p>务实点儿讲,匿名函数的递归调用,在日常的js开发中,用到的真的很少。把这个问题拿出来讲,主要是想引出对<code>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递归调用有差不多一个数量级的差异,将不定点函数算出后保存下来,大概会有一倍左右的性能提升。
以上就是JavaScript 中匿名函数的递归调用的代码详细介绍的内容,更多相关内容请关注PHP中文网(www.php.cn)!