JavaScript コールスタック、末尾再帰、手動最適化の詳細な紹介

この記事では、JavaScriptコールスタック、テール再帰、および手動最適化についての詳細な説明を主に紹介します。興味のある方は、

Call Stack (Call Stack)を参照してください。スタックはコンピュータの基本的な概念です。ここでスタック フレームという概念を紹介します。

スタックフレームは、

関数

呼び出し用に個別に割り当てられたスタックスペースの部分を指します。
実行中のプログラムが現在の関数から別の関数を呼び出すと、次の関数のために新しいスタック フレームが作成され、このスタック フレームが現在のフレームと呼ばれます。元の関数には、呼び出しフレームと呼ばれる、対応するスタック フレームもあります。各スタック フレームには、現在の関数のローカル

変数

が保存されます。

関数が呼び出されると、その関数は呼び出しスタックの先頭に追加され、実行が完了すると、関数は呼び出しスタックの先頭から削除されます。そしてこのときスタックの最上位にあるスタックフレームへの実行権（フレームポインタ）をプログラムに与えます。この後入れ後出し構造が関数の呼び出しスタックです。

JavaScript では、console.trace() メソッドを通じて現在の関数の呼び出しフレームを簡単に表示できます

末尾呼び出し

末尾再帰について話す前に、まず末尾呼び出しとは何かを理解する必要がありますは。簡単に言えば、関数実行の最後のステップは、別の関数を呼び出して戻ることです。

以下は正しいデモです:

// 尾调用正确示范1.0
function f(x){
 return g(x);
}

// 尾调用正确示范2.0
function f(x) {
 if (x > 0) {
  return m(x)
 }
 return n(x);
}

1.0 プログラムの最後のステップは、関数 g を実行し、同時にその戻り値を返すことです。 2.0 では、実行時の最後のステップである限り、末尾呼び出しを最後の行に記述する必要はありません。

以下はエラーのデモです:

// 尾调用错误示范1.0
function f(x){
 let y = g(x);
 return y;
}

// 尾调用错误示范2.0
function f(x){
 return g(x) + 1;
}
// 尾调用错误示范3.0
function f(x) {
 g(x); // 这一步相当于g(x) return undefined
}

1.0 の最後のステップは代入演算、2.0 の最後のステップは加算演算、3.0 には暗黙的な戻り値が未定義です

テール呼び出しの最適化

コールスタック部分については、関数 A が別の関数 B を呼び出すと、スタック フレームが形成されます。呼び出しスタックには、呼び出し元のフレーム A と現在のフレーム B の両方が存在します。これは、関数 B の実行後に発生するためです。関数A内の変数や関数Bの呼び出し位置などを呼び出しフレームAに保存する必要があります。そうしないと、関数 B の実行が終了し、関数 A の実行を継続したときに、すべてがうまくいかなくなります。

それでは、関数 A の最後の呼び出し (つまり、末尾の呼び出し) に関数 B を入れます。関数 A のスタック フレームを保持する必要がありますか?もちろん、その呼び出し位置と内部変数は再度使用されないため、そうではありません。したがって、関数 A のスタック フレームを関数 B のスタック フレームに置き換えるだけです。もちろん、内部関数が外部関数の変数を使用する場合でも、関数 A のスタック フレームを保持する必要があります。典型的な例はクロージャです。

インターネット上にはテールコールについて説明したブログ記事がたくさんありますが、最も広く流通している記事の 1 つに次の段落があります。私はあまり同意しません。

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 の呼び出し位置、その他の情報を保存する必要があります。ただし、関数 f は g を呼び出した後に終了するため、実行の最後のステップで f() の呼び出し記録を削除し、g(3) の呼び出し記録のみを保持することができます。

しかし、最初のメソッドも最初に m+n ステップを実行し、次に関数 g を呼び出して同時に返すと思います。これはテールコールである必要があります。同時に、m+n の値もパラメータを介して関数 g に渡され、直接参照されないため、f 内の変数の値を保存する必要があるとは言えません。

一般に、すべての関数呼び出しが末尾呼び出しである場合、呼び出しスタックの長さははるかに小さくなり、必要なメモリも大幅に削減されます。これが末尾呼び出しの最適化の意味です。

末尾再帰

再帰とは、関数

自体を関数の定義の中で利用する方法を指します。自分自身を呼び出す関数を再帰といい、最後に自分自身を呼び出す関数を末尾再帰といいます。

最も一般的な再帰、フィボナッチ数列、通常の再帰の書き方:

function f(n) {
 if (n === 0 || n === 1) return n 
 else return f(n - 1) + f(n - 2)
}

この書き方は単純で大雑把ですが、非常に深刻な問題があります。呼び出しスタックは、n の増加に伴って直線的に増加します。n が大きい場合 (私がテストしたところ、n が 100 の場合、ブラウザー ウィンドウがフリーズします...)、スタックはバースト (スタック オーバーフロー) し、スタック オーバーフロー

になります。 ）。これは、この再帰的な操作では、同時に大量のスタック フレームが保存され、呼び出しスタックが非常に長くなり、大量のメモリが消費されるためです。

接下来，将普通递归升级为尾递归看看。

function fTail(n, a = 0, b = 1) { 
 if (n === 0) return a
 return fTail(n - 1, b, a + b)
}

很明显，其调用栈为

 代码如下:

fTail(5) => fTail(4, 1, 1) => fTail(3, 1, 2) => fTail(2, 2, 3) => fTail(1, 3, 5) => fTail(0, 5, 8) => return 5

被尾递归改写之后的调用栈永远都是更新当前的栈帧而已，这样就完全避免了爆栈的危险。

但是，想法是好的，从尾调用优化到尾递归优化的出发点也没错，然并卵：），让我们看看V8引擎官方团队的解释

Proper tail calls have been implemented but not yet shipped given that a change to the feature is currently under discussion at TC39.

意思就是人家已经做好了，但是就是还不能不给你用：）嗨呀，好气喔。

当然，人家肯定是有他的正当理由的：

1. 在引擎层面消除尾递归是一个隐式的行为，程序员写代码时可能意识不到自己写了死循环的尾递归，而出现死循环后又不会报出stack overflow的错误，难以辨别。

2. 堆栈信息会在优化的过程中丢失，开发者调试非常困难。

道理我都懂，但是不信邪的我拿nodeJs（v6.9.5）手动测试了一下：

好的，我服了

手动优化

虽然我们暂时用不上ES6的尾递归高端优化，但递归优化的本质还是为了减少调用栈，避免内存占用过多，爆栈的危险。而俗话说的好，一切能用递归写的函数，都能用循环写——尼克拉斯·夏，如果将递归改成循环的话，不就解决了这种调用栈的问题么。

方案一：直接改函数内部，循环执行

function fLoop(n, a = 0, b = 1) { 
 while (n--) {
  [a, b] = [b, a + b]
 }
 return a
}

这种方案简单粗暴，缺点就是没有递归的那种写法比较容易理解。

方案二：Trampolining（蹦床函数）

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

function f(n, a = 0, b = 1) { 
 if (n > 0) {
  [a, b] = [b, a + b]
  return f.bind(null, n - 1, a, b)
 } else {
  return a
 }
}

trampoline(f(5)) // return 5

这种写法算是容易理解一些了，就是蹦床函数的作用需要仔细看看。缺点还有就是需要修改原函数内部的写法。

方案三：尾递归函数转循环方法

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

const f = tailCallOptimize(function(n, a = 0, b = 1) { 
 if (n === 0) return a
 return f(n - 1, b, a + b)
})
f(5) // return 5

经过 tailCallOptimize 包装后返回的是一个新函数 accumulator，执行 f时实际执行的是这个函数。这种方法可以不用修改原递归函数，当调用递归时只用使用该方法转置一下便可解决递归调用的问题。

总结

尾递归优化是个好东西，但既然暂时用不上，那我们就该在平时编码的过程中，对使用到了递归的地方特别敏感，时刻避免出现死循环，爆栈等危险。毕竟，好的工具不如好的习惯。

以上がJavaScript コールスタック、末尾再帰、手動最適化の詳細な紹介の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。