再帰とスタック

関数に戻り、より詳細に調べてみましょう。

最初のトピックは再帰です。

プログラミング初心者でない場合は、おそらく馴染みがあり、この章をスキップしても構いません。

再帰は、タスクを自然に同じ種類のいくつかのより単純なタスクに分割できる場合、またはタスクを簡単な操作と同一タスクのより単純なバリアントに単純化できる場合に役立つプログラミングパターンです。あるいは、すぐにわかるように、特定のデータ構造を扱うためにも使用できます。

関数がタスクを解決する際、その過程で多くの他の関数を呼び出すことができます。その部分的なケースとして、関数が自分自身を呼び出すというものがあります。それが再帰と呼ばれます。

2つの考え方

まずは簡単なものとして、xを自然数n乗する関数pow(x, n)を書いてみましょう。言い換えれば、xをn回自身で乗算します。

pow(2, 2) = 4
pow(2, 3) = 8
pow(2, 4) = 16

実装するには2つの方法があります。

1. 反復的な考え方：`for`ループ

   function pow(x, n) {
     let result = 1;
   
     // multiply result by x n times in the loop
     for (let i = 0; i < n; i++) {
       result *= x;
     }
   
     return result;
   }
   
   alert( pow(2, 3) ); // 8

2. 再帰的な考え方：タスクを単純化して自己呼び出しを行う

   function pow(x, n) {
     if (n == 1) {
       return x;
     } else {
       return x * pow(x, n - 1);
     }
   }
   
   alert( pow(2, 3) ); // 8

再帰的なバリアントが根本的に異なることに注意してください。

pow(x, n)が呼び出されると、実行は2つのブランチに分岐します。

              if n==1  = x
             /
pow(x, n) =
             \
              else     = x * pow(x, n - 1)

1. n == 1の場合、すべてが自明です。これは再帰の基底と呼ばれ、自明な結果pow(x, 1)はxに等しくなります。
2. それ以外の場合は、pow(x, n)をx * pow(x, n - 1)として表すことができます。数学では、xn = x * xn-1と書きます。これは再帰ステップと呼ばれ、タスクをより単純な操作（xによる乗算）と同一タスクのより単純な呼び出し（nが小さいpow）に変換します。次のステップでは、nが1に達するまで、さらに単純化されます。

n == 1になるまで、powが自分自身を再帰的に呼び出すともいえます。

たとえば、pow(2, 4)を計算するために、再帰的なバリアントはこれらのステップを実行します。

1. pow(2, 4) = 2 * pow(2, 3)
2. pow(2, 3) = 2 * pow(2, 2)
3. pow(2, 2) = 2 * pow(2, 1)
4. pow(2, 1) = 2

したがって、再帰は関数呼び出しをより単純なものに、そしてさらに単純なものに減らし、結果が自明になるまで続けます。

function pow(x, n) {
  return (n == 1) ? x : (x * pow(x, n - 1));
}

ネストされた呼び出しの最大数（最初の呼び出しを含む）は、再帰深度と呼ばれます。この場合、正確にnになります。

再帰深度はJavaScriptエンジンによって制限されています。10000とすることができますが、一部のエンジンではそれ以上を許容しますが、100000はほとんどのエンジンではおそらく制限を超えています。これを軽減する自動最適化（「テールコール最適化」）がありますが、まだどこでもサポートされているわけではなく、単純なケースでのみ機能します。

これは再帰の適用を制限しますが、それでも非常に広範なままです。再帰的な考え方がよりシンプルで保守しやすいコードを提供する多くのタスクがあります。

実行コンテキストとスタック

次に、再帰呼び出しがどのように機能するかを調べましょう。そのためには、関数の内部を調べます。

実行中の関数の実行プロセスに関する情報は、その実行コンテキストに格納されます。

実行コンテキストは、関数の実行に関する詳細（制御フローの現在位置、現在の変数、thisの値（ここでは使用していません）、その他のいくつかの内部詳細）を含む内部データ構造です。

1つの関数呼び出しには、それに関連付けられた実行コンテキストが正確に1つあります。

関数がネストされた呼び出しを行うと、次のようになります。

• 現在の関数が一時停止します。
• それに関連付けられた実行コンテキストは、実行コンテキストスタックと呼ばれる特別なデータ構造に記憶されます。
• ネストされた呼び出しが実行されます。
• それが終了すると、古い実行コンテキストがスタックから取得され、外部関数は中断した場所から再開されます。

pow(2, 3)呼び出し中に何が起こるかを見てみましょう。

pow(2, 3)

pow(2, 3)呼び出しの開始時、実行コンテキストには変数x = 2, n = 3が格納され、実行フローは関数の1行目になります。

それを次のようにスケッチできます。

• コンテキスト：{ x: 2, n: 3, 1行目 } pow(2, 3)

関数が実行を開始します。条件n == 1は偽なので、フローはifの2番目のブランチに進みます。

function pow(x, n) {
  if (n == 1) {
    return x;
  } else {
    return x * pow(x, n - 1);
  }
}

alert( pow(2, 3) );

変数は同じですが、行が変わるため、コンテキストは次のようになります。

• コンテキスト：{ x: 2, n: 3, 5行目 } pow(2, 3)

x * pow(x, n - 1)を計算するには、新しい引数pow(2, 2)でpowのサブ呼び出しを行う必要があります。

pow(2, 2)

ネストされた呼び出しを行うために、JavaScriptは現在の実行コンテキストを実行コンテキストスタックに記憶します。

ここでは同じ関数powを呼び出しますが、まったく問題ありません。すべての関数でプロセスは同じです。

1. 現在のコンテキストはスタックの一番上に「記憶」されます。
2. サブ呼び出しのために新しいコンテキストが作成されます。
3. サブ呼び出しが終了すると、前のコンテキストがスタックからポップされ、その実行が再開されます。

サブ呼び出しpow(2, 2)に入ったときのコンテキストスタックを次に示します。

• コンテキスト：{ x: 2, n: 2, 1行目 } pow(2, 2)
• コンテキスト：{ x: 2, n: 3, 5行目 } pow(2, 3)

新しい現在の実行コンテキストが一番上にあり（太字）、以前に記憶されたコンテキストはその下にあります。

サブ呼び出しが終了すると、変数と停止したコードの正確な場所の両方を保持しているため、前のコンテキストを簡単に再開できます。

pow(2, 1)

プロセスが繰り返されます。新しいサブ呼び出しが5行目で、引数はx=2、n=1になります。

新しい実行コンテキストが作成され、前のコンテキストがスタックの一番上にプッシュされます。

• コンテキスト：{ x: 2, n: 1, 1行目 } pow(2, 1)
• コンテキスト：{ x: 2, n: 2, 5行目 } pow(2, 2)
• コンテキスト：{ x: 2, n: 3, 5行目 } pow(2, 3)

現在、pow(2, 1)に対して2つの古いコンテキストと1つの実行中のコンテキストがあります。

終了

pow(2, 1)の実行中、前とは異なり、条件n == 1は真なので、ifの最初のブランチが機能します。

function pow(x, n) {
  if (n == 1) {
    return x;
  } else {
    return x * pow(x, n - 1);
  }
}

ネストされた呼び出しはもうないので、関数は終了し、2を返します。

関数が終了すると、その実行コンテキストはもう必要ないので、メモリから削除されます。前のコンテキストがスタックの一番上から復元されます。

• コンテキスト：{ x: 2, n: 2, 5行目 } pow(2, 2)
• コンテキスト：{ x: 2, n: 3, 5行目 } pow(2, 3)

pow(2, 2)の実行が再開されます。サブ呼び出しpow(2, 1)の結果があるので、x * pow(x, n - 1)の評価も終了し、4を返すことができます。

次に、前のコンテキストが復元されます。

• コンテキスト：{ x: 2, n: 3, 5行目 } pow(2, 3)

それが終了すると、pow(2, 3) = 8の結果が得られます。

この場合の再帰深度は3です。

上記の図からわかるように、再帰深度はスタック内のコンテキストの最大数に等しくなります。

メモリの要件に注意してください。コンテキストはメモリを消費します。この場合、n乗するには、nのすべての小さい値に対して、n個のコンテキストのメモリが必要です。

ループベースのアルゴリズムの方がメモリ効率が良い

function pow(x, n) {
  let result = 1;

  for (let i = 0; i < n; i++) {
    result *= x;
  }

  return result;
}

反復的なpowは、プロセスでiとresultを変更する単一のコンテキストを使用します。そのメモリの要件は小さく、固定されており、nに依存しません。

再帰はすべてループとして書き直すことができます。ループのバリアントは通常、より効率的にすることができます。

…しかし、関数が条件に応じて異なる再帰的サブコールを使用し、その結果をマージする場合、または分岐がより複雑な場合は、書き換えが自明でない場合があります。そして、最適化は不要であり、努力に見合う価値がない可能性があります。

再帰は、より短く、理解しやすく、サポートしやすいコードを提供できます。最適化はあらゆる場所で必要というわけではなく、ほとんどの場合、良いコードが必要なので、再帰が使用されます。

再帰的トラバーサル

再帰のもう一つの優れた用途は、再帰的トラバーサルです。

会社があると想像してください。スタッフの構造はオブジェクトとして表現できます。

let company = {
  sales: [{
    name: 'John',
    salary: 1000
  }, {
    name: 'Alice',
    salary: 1600
  }],

  development: {
    sites: [{
      name: 'Peter',
      salary: 2000
    }, {
      name: 'Alex',
      salary: 1800
    }],

    internals: [{
      name: 'Jack',
      salary: 1300
    }]
  }
};

言い換えれば、会社には部門があります。

• 部門にはスタッフの配列が含まれる場合があります。たとえば、`sales` 部門には、John と Alice の2人の従業員がいます。

• または、部門はサブ部門に分割される場合があります。たとえば、`development` は `sites` と `internals` の2つの部門に分かれています。それぞれに独自のスタッフがいます。

• サブ部門が成長すると、サブサブ部門（またはチーム）に分割されることも可能です。

  たとえば、将来、`sites` 部門は `siteA` と `siteB` のチームに分割される可能性があります。そして、それらはさらに分割される可能性があります。図には示されていませんが、念頭に置いておくべきことです。

さて、すべての給与の合計を取得する関数を作成したいとします。どのようにすればよいでしょうか？

構造が単純ではないため、反復的なアプローチは容易ではありません。最初のアイデアは、1レベル目の部門のネストされたサブループで`company`に対して`for`ループを作成することかもしれません。しかし、その後、`sites`のような2レベル目の部門のスタッフを反復処理するために、さらにネストされたサブループが必要になります…そして、将来表示される可能性のある3レベル目の部門に対して、それらの内部に別のサブループが必要になりますか？単一オブジェクトをトラバースするためにコードに3〜4個のネストされたサブループを配置すると、かなり見にくくなります。

再帰を試してみましょう。

ご覧のとおり、関数が合計する部門を取得すると、2つのケースが考えられます。

1. それは、人々の_配列_を持つ「単純な」部門です。— その場合、単純なループで給与の合計を求めることができます。
2. または、`N`個のサブ部門を持つ_オブジェクト_です。— その場合、各サブ部門の合計を取得するために`N`回の再帰呼び出しを行い、結果を組み合わせることができます。

最初のケースは再帰の基礎であり、自明なケースです。配列を取得した場合です。

オブジェクトを取得する2番目のケースは、再帰ステップです。複雑なタスクは、より小さな部門のサブタスクに分割されます。それらは順番に再び分割される可能性がありますが、遅かれ早かれ、分割は(1)で終了します。

アルゴリズムは、コードからさらに読みやすいかもしれません。

let company = { // the same object, compressed for brevity
  sales: [{name: 'John', salary: 1000}, {name: 'Alice', salary: 1600 }],
  development: {
    sites: [{name: 'Peter', salary: 2000}, {name: 'Alex', salary: 1800 }],
    internals: [{name: 'Jack', salary: 1300}]
  }
};

// The function to do the job
function sumSalaries(department) {
  if (Array.isArray(department)) { // case (1)
    return department.reduce((prev, current) => prev + current.salary, 0); // sum the array
  } else { // case (2)
    let sum = 0;
    for (let subdep of Object.values(department)) {
      sum += sumSalaries(subdep); // recursively call for subdepartments, sum the results
    }
    return sum;
  }
}

alert(sumSalaries(company)); // 7700

コードは短く、理解しやすいです（願わくば？）。それが再帰の力です。これは、任意のレベルのサブ部門のネストにも機能します。

これが呼び出しのダイアグラムです。

原則は簡単にわかります。オブジェクト`{...}`に対してはサブコールが行われ、配列`[...]`は再帰ツリーの「葉」であり、即座に結果を与えます。

コードは、以前に説明したスマートな機能を使用していることに注意してください。

• 配列の合計を取得するための`arr.reduce`メソッドは、配列メソッドの章で説明されています。
• オブジェクトの値を反復処理するためのループ`for(val of Object.values(obj))`：`Object.values`はそれらの配列を返します。

再帰的構造

再帰的（再帰的に定義された）データ構造とは、一部で自己複製する構造のことです。

これは、上記の会社の構造の例で既に見てきました。

会社の_部門_は

• 人の配列です。
• または、_部門_を持つオブジェクトです。

Web開発者にとって、HTMLとXMLドキュメントははるかによく知られた例です。

HTMLドキュメントでは、_HTMLタグ_には、次のリストが含まれる場合があります。

• テキスト部分。
• HTMLコメント。
• 他の_HTMLタグ_（順番にテキスト部分/コメントまたはその他のタグなどを含む可能性があります）。

これもまた再帰的な定義です。

より良い理解のために、「連結リスト」というもう1つの再帰構造について説明します。これは、場合によっては配列のより良い代替手段となる可能性があります。

連結リスト

オブジェクトの順序付きリストを保存したいとします。

自然な選択は配列です。

let arr = [obj1, obj2, obj3];

…しかし、配列には問題があります。「要素の削除」と「要素の挿入」操作はコストがかかります。たとえば、`arr.unshift(obj)`操作では、新しい`obj`のためのスペースを作るためにすべての要素の番号を付け直す必要があり、配列が大きい場合は時間がかかります。`arr.shift()`でも同様です。

大量の番号付け直しを必要としない構造上の変更は、配列の末尾を操作するものだけです：`arr.push/pop`。そのため、配列の先頭で作業する必要がある場合、大きなキューに対して配列は非常に遅くなる可能性があります。

代わりに、本当に高速な挿入/削除が必要な場合は、連結リストと呼ばれる別のデータ構造を選択できます。

_連結リスト要素_は、次のもので再帰的に定義されたオブジェクトです。

• 値.
• 次の_連結リスト要素_を参照する`next`プロパティ、またはそれが最後の場合`null`。

たとえば

let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};

リストのグラフィカル表現

作成のための代替コード

let list = { value: 1 };
list.next = { value: 2 };
list.next.next = { value: 3 };
list.next.next.next = { value: 4 };
list.next.next.next.next = null;

ここでは、複数のオブジェクトがあり、それぞれに`value`があり、`next`が隣接要素を指していることがさらに明確にわかります。`list`変数はチェーンの最初のオブジェクトであるため、そこから`next`ポインタをたどると、任意の要素に到達できます。

リストは簡単に複数の部分に分割し、後で結合することができます。

let secondList = list.next.next;
list.next.next = null;

結合するには

list.next.next = secondList;

そしてもちろん、任意の場所にアイテムを挿入または削除できます。

たとえば、新しい値を先頭に追加するには、リストの先頭を更新する必要があります。

let list = { value: 1 };
list.next = { value: 2 };
list.next.next = { value: 3 };
list.next.next.next = { value: 4 };

// prepend the new value to the list
list = { value: "new item", next: list };

中央から値を削除するには、前のものの`next`を変更します。

list.next = list.next.next;

`list.next`を`1`から`2`にジャンプさせました。値`1`はチェーンから除外されています。他の場所に保存されていない場合は、メモリから自動的に削除されます。

配列とは異なり、大量の番号付け直しは必要ありません。要素を簡単に並べ替えることができます。

もちろん、リストは常に配列よりも優れているわけではありません。そうであれば、誰もリストだけを使用するでしょう。

主な欠点は、番号で要素に簡単にアクセスできないことです。配列では簡単です：`arr[n]`は直接参照です。しかし、リストでは、最初のアイテムから開始し、`next`を`N`回移動してN番目の要素を取得する必要があります。

…しかし、そのような操作は常に必要というわけではありません。たとえば、キュー、またはデック（両端への要素の追加/削除を非常に高速に行う必要がある順序付けられた構造だが、中央へのアクセスは必要ない）が必要な場合などです。

リストは拡張できます。

• 前の要素を参照する`next`に加えて`prev`プロパティを追加して、簡単に後ろに移動することができます。
• リストの最後の要素を参照する`tail`という名前の変数を追加し（そして、末尾から要素を追加/削除するときにそれを更新します）、
• …データ構造は、ニーズに合わせて変更できます。

要約

用語

• _再帰_とは、関数が自分自身を呼び出すことを意味するプログラミング用語です。再帰関数は、エレガントな方法でタスクを解決するために使用できます。

  関数が自分自身を呼び出すことを、_再帰ステップ_と言います。再帰の_基礎_は、タスクを非常に単純にする関数引数であり、関数はそれ以上の呼び出しを行いません。

• 再帰的に定義されたデータ構造とは、それ自体を使用して定義できるデータ構造のことです。

  たとえば、連結リストは、リスト（またはnull）を参照するオブジェクトで構成されるデータ構造として定義できます。

  list = { value, next -> list }

  HTML要素ツリーやこの章の部門ツリーのようなツリーも、自然に再帰的です。枝があり、すべての枝に他の枝を持つことができます。

  `sumSalary`の例で見たように、再帰関数はそれらをたどるために使用できます。

任意の再帰関数は、反復関数に書き直すことができます。そして、それは時々物事を最適化するのに必要です。しかし、多くのタスクでは、再帰的なソリューションは十分に高速であり、記述およびサポートが容易です。