ES 6尾呼び出しと最後再帰

最近ES 6を復習しています.最後の呼出を勉強しましたので、いくつかの摘録と結び目を作りました.
テイルコールとは?
テイルコールは関数式プログラミングの重要な概念です.それ自体はとても簡単です.一言ではっきり言えます.つまり、ある関数の最後のステップは別の関数を呼び出すことです.

function f(x){
  return g(x);
}

上のコードでは、関数fの最後のステップは、関数gを呼び出します.以下の3つの場合は、いずれもテールコールに該当しません.

//    
function f(x){
  let y = g(x);
  return y;
}

//    
function f(x){
  return g(x) + 1;
}

//    
function f(x){
  g(x);
}

上のコードの場合、一は関数gを呼び出した後に、赋値操作がありますので、語義が完全に同じでも、テイルコールではありません.状況二も呼出後に操作があります.一行に書いてもいいです.ケース3は下記のコードと同じです.

function f(x){
  g(x);
  return undefined;
}

最後のステップで操作すればいいです.

function f(x) {
  if (x > 0) {
    return m(x)
  }
  return n(x);
}

上のコードでは、関数mとnは、関数fの最後のステップであるので、テイルコールに属しています.
厳格モード
ES 6の終端呼び出し最適化は、厳格なモードでのみ開かれ、通常モードは無効です.これは、通常モードでは関数内部に2つの変数があり、関数のコールスタックを追跡することができるからです.

* func.arguments：          。
* func.caller：             。

最後の呼び出し最適化が発生すると、関数の呼び出しスタックが書き換えられますので、上の二つの変数が歪みます.厳密モードではこの2つの変数を無効にしますので、テイルコールモードは厳密モードでのみ有効です.

function restricted() {
  'use strict';
  restricted.caller;    //   
  restricted.arguments; //   
}
restricted();

テールコール最適化
最後の呼び出しが他の呼び出しと異なるのは、その特殊な呼び出し位置にあるからです.関数コールはメモリに「呼び出し記録」を形成し、また「呼び出しフレーム」とも呼ばれ、呼び出し位置や内部変数などの情報を保存することを知っています.関数Aの内部で関数Bを呼び出すと、Aの呼び出しフレームの上にBの呼び出しフレームが形成される.B運転が完了すると、結果をAに戻し、Bの呼び出しフレームが消えます.関数Bの内部で関数Cが呼び出されると、Cの呼び出しフレームがもう一つあり、これに類推する.すべての呼び出しフレームは、「呼び出しスタック」を形成する.テイルコールは関数の最後のステップですので、外部関数の呼び出しフレームを保留する必要はありません.呼び出し位置、内部変数などの情報はもう使用できません.外部関数の呼び出しフレームに代えて、直接にイントラ関数の呼び出しフレームを使えばいいです.

function f() {
  let m = 1;
  let n = 2;
  return g(m + n);
}
f();

//    
function f() {
  return g(3);
}
f();

//    
g(3);

上のコードでは、関数gがテイルコールではない場合、関数fは内部変数mとnの値、gの呼び出し位置などの情報を保存する必要があります.しかし、gを呼び出した後、関数fは終了するので、最後のステップまで実行すれば、f(x)の呼び出しフレームは完全に削除され、g(3)の呼び出しフレームだけを保留することができる.
これは、「テイルコール最適化」と呼ばれ、すなわち、イントラ関数の呼び出しフレームのみを保持します.すべての関数が最後の呼び出しであれば、実行するたびに、呼び出しフレームは一つしかないので、メモリを大いに節約することができます.これが「テールコール最適化」という意味です.
なお、外部関数の内部変数を使用しない限り、内部関数の呼び出しフレームは外層関数の呼び出しフレームに取って代わることができ、そうでなければ「テール呼び出し最適化」はできない.

function addOne(a){
  var one = 1;
  function inner(b){
    return b + one;
  }
  return inner(a);
}

上の関数は、内層関数innerが外層関数addOneの内部変数oneを使用しているので、テールコール最適化は行われません.なお、現在はSafariブラウザのみがフォローアップをサポートしており、ChromeとFirefoxはサポートされていません.
最終再帰的最適化
関数が自身を呼び出して再帰と呼びます.最後に自身を呼び出したら、最後の再帰と呼びます.再帰的にはメモリが非常に消費されます.何千何百個もの呼び出しフレームを同時に保存する必要があるので、「スタックオーバーフロー」エラーが発生しやすいです.しかし、最終再帰的には、呼び出しフレームが一つしか存在しないため、「スタックオーバーフロー」エラーは永遠に発生しない.

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

factorial(5) // 120

上のコードは階乗関数で、nの階乗を計算します.最大nコール記録、複雑度O(n)を保存する必要があります.
最後の再帰的に書き換えた場合、呼び出し記録は1つだけ残し、複雑度O(1).

function factorial(n, total) {
  if (n === 1) return total;
  return factorial(n - 1, n * total);
}

factorial(5, 1) // 120

もう一つ有名な例があります.フィボナッチの数列を計算しても、最後の再帰最適化の重要性を十分に説明できます.
非後戻りのFibonacci数列は以下の通り実現される.

function Fibonacci (n) {
  if ( n <= 1 ) {return 1};

  return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Fibonacci(10) // 89
Fibonacci(100) //   
Fibonacci(500) //   

最後の再帰的最適化されたFibonacci数列は以下の通り実現される.

function Fibonacci2 (n , ac1 = 1 , ac2 = 1) {
  if( n <= 1 ) {return ac2};

  return Fibonacci2 (n - 1, ac2, ac1 + ac2);
}

Fibonacci2(100) // 573147844013817200000
Fibonacci2(1000) // 7.0330367711422765e+208
Fibonacci2(10000) // Infinity

これから分かるように、「尻呼び出し最適化」は再帰的な操作に大きな意味を持っているので、いくつかの関数式プログラミング言語は言語規格に書き込みました.ES 6もこのようにして、初めて明確に規定されました.すべてのECMAScriptの実現には、「最後呼び出し最適化」が必要です.つまり、ES 6では、最終的な再帰的なものを使用すると、スタックオーバーフロー(または再帰的に発生するタイムアウト)が発生せず、メモリの節約が相対的に行われる.
再帰関数の書き換え
再帰的な実装は、再帰関数を書き換える必要があり、最後のステップは自分自身だけで呼び出されるようにする.このようにする方法は、使用する内部変数をすべて関数のパラメータに書き換えることです.例えば上記の例では、階乗関数factoralは中間変数totalを使用する必要があります.この中間変数を関数のパラメータに書き換えます.このようにする欠点はあまり直観的ではなく、第一目はとても醜くて、どうして5の階乗を計算して、2つのパラメータ5と1に入る必要がありますか?
二つの方法はこの問題を解決できる.方法の1つは、末尾再帰関数に加えて、通常の形式の関数を提供することである.

function tailFactorial(n, total) {
  if (n === 1) return total;
  return tailFactorial(n - 1, n * total);
}

function factorial(n) {
  return tailFactorial(n, 1);
}

factorial(5) // 120

上のコードは通常の形の階乗関数factoralを通して、最後の再帰関数tailFactorialを呼び出します.正常に多く見られます.
関数式プログラミングには、複数パラメータの関数を単一パラメータに変換するという概念があります.ここでもコリ化ができます.

function currying(fn, n) {
  return function (m) {
    return fn.call(this, m, n);
  };
}

function tailFactorial(n, total) {
  if (n === 1) return total;
  return tailFactorial(n - 1, n * total);
}

const factorial = currying(tailFactorial, 1);

factorial(5) // 120

上のコードはコリック化によって、最後の再帰関数tailFactorialを一つのパラメータだけを受け入れるfactorialになります.
第二の方法は簡単に多くなります.つまりES 6の関数のデフォルト値を採用します.

function factorial(n, total = 1) {
  if (n === 1) return total;
  return factorial(n - 1, n * total);
}

factorial(5) // 120

上のコードでは、パラメータtotalはデフォルト値1がありますので、呼び出し時にはこの値を提供する必要はありません.
まとめてみます.再帰は本質的には循環操作です.純粋な関数式プログラミング言語には循環操作コマンドがありません.すべての循環は再帰的に実現されます.他の「テール呼び出し最適化」をサポートする言語(例えば、Lua、ES 6)については、サイクルが再帰的に代替されることを知っているだけで、再帰的に使用されると、最後の再帰的なものが望ましい.
最終再帰的最適化の実現
最終的な再帰的最適化は厳格なモードでのみ有効になります.正常なモードで、またはその機能をサポートしない環境で、最終的な再帰的最適化を使用する方法がありますか?答えは可能です.つまり自分で最終的な再帰的最適化を実現します.
その原理はとても簡単です.再帰的に最適化が必要なのは、スタックの呼び出しが多すぎてオーバーフローが発生したからです.どうすればコールスタックを減らすことができますか?「循環」を使って「再帰」を換えます.
以下は正常な再帰関数です.

function sum(x, y) {
  if (y > 0) {
    return sum(x + 1, y - 1);
  } else {
    return x;
  }
}

sum(1, 100000)
// Uncaught RangeError: Maximum call stack size exceeded(…)

上のコードでは、sumは再帰関数であり、パラメータxは積算が必要な値であり、パラメータyは再帰回数を制御する.sum再帰を100000回指定すると、呼び出しスタックの最大回数を超えてエラーが発生します.トランポリン関数(trmpoline)は再帰的な実行を循環的に実行することができます.

function trampoline(f) {
  while (f && f instanceof Function) {
    f = f();
  }
  return f;
}

上はトランポリンの関数の一つです.パラメータとして関数fを受け取ります.fが実行された後に関数を返す限り、実行を続けます.ここでは関数を返して関数を実行します.再帰的な実行を回避することで、スタックの呼び出しがあまりにも大きい問題が解消されます.
そして、元の再帰関数を各ステップに書き換えて別の関数に戻します.

function sum(x, y) {
  if (y > 0) {
    return sum.bind(null, x + 1, y - 1);
  } else {
    return x;
  }
}

上のコードは、sum関数が実行されるたびに、自身の別のバージョンに戻ります.現在、トランポリン関数を使ってsumを実行すると、スタックオーバーフローが発生しません.

trampoline(sum(1, 100000))
// 100001

トランポリンの機能は本当の最後の再帰的最適化ではなく、次の実現こそです.

function tco(f) {
  var value;
  var active = false;
  var accumulated = [];

  return function accumulator() {
    accumulated.push(arguments);
    if (!active) {
      active = true;
      while (accumulated.length) {
        value = f.apply(this, accumulated.shift());
      }
      active = false;
      return value;
    }
  };
}

var sum = tco(function(x, y) {
  if (y > 0) {
    return sum(x + 1, y - 1)
  }
  else {
    return x
  }
});

sum(1, 100000)
// 100001

上記のコードの中で、tco関数は最終再帰的最適化の実現であり、その奥妙は状態変数activeにあります.デフォルトでは、この変数は非アクティブです.最後の再帰的最適化のプロセスに入ると、この変数はアクティブになります.その後、再帰的sumはundefinedで返されるので、再帰的な実行は避けられます.accumullated配列はsum毎に実行されるパラメータを格納し、常に値がある.これはaccumultor関数内部のwhileサイクルが常に実行されることを保証する.
このように「再帰」を巧みに「循環」に変え、その後、一輪のパラメータは前のラウンドのパラメータに取って代わります.
推荐阅覧:【テーマ:JavaScript进级的路】JavaScriptの深度理解クローズドJavaScriptの「use strit」JavaScriptのnew演算子JavaScriptのcall()理解JavaScriptの対象属性
私はCloudyです.若い先端で城を攻める獅子です.専門研究を愛し、技術を愛し、分かち合います.
個人のノート、整理は簡単ではありませんて、読んで、点の賛美と収集に感謝します.
文章には何か問題があります.ご指摘ください.先端の問題も一緒に交流してください.