2021年12月15日

再帰とスタック

ここでは関数に戻り、より深く学びましょう。

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

あなたがプログラミング初心者でないなら、おそらく馴染みのある内容なのでこのチャプターをスキップしても問題ありません。

再帰は、タスクを同じ種類の複数のタスクに分割することができる状況で役立つプログラミングパターンで、よりシンプルに実現することができます。あるいは、タスクを簡単なアクションと同じタスクのよりシンプルなパターンに単純化できる場合や、この後すぐに見ていきますが特定のデータ構造を扱う場合にも役立ちます。

関数がタスクを解決するとき、処理の過程で多くの他の関数を呼ぶことができます。この部分的なケースとして、関数が 自分自身 を呼ぶときです。それは 再帰 と呼ばれます。

2つの考え方

初めのシンプルな例として、xn 乗をする関数 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;
    
      // ループで、n 回結果を x で乗算する
      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)に変換します。次のステップではそれをさらに単純化し、n1 になるまで単純化されます。

pown == 1 まで 再帰的に自分自身を呼び出す 、とも言えます。

例えば、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

したがって、再帰は関数呼び出しをより簡単なものに変換し、それを結果が明白になるまで繰り返します。

通常、再帰はより短く書けます

再帰的な解決策は、通常、反復する方法よりも短いです。

ここで、pow(x, n) をより簡潔にし、かつ読みやすくするために if の代わりに3項演算子 ? を使って書き直すことができます。:

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

入れ子呼び出しの最大数(最初の1回を含む)は 再帰の深さ と呼ばれます。我々のケースでは、それは n になります。

最大の再帰の深さは JavaScript エンジンによって制限されています。10,000 は確実で、エンジンによってはより多くの値が可能ですが、100,000 は恐らく大多数の制限を超えます。これを緩和する自動最適もあります(“末尾再帰”)が、どこでもサポートされているわけではなく、単純なケースでのみ機能します。

それは再帰の使用を制限しますが、依然として非常に広範囲に使われています。再帰的な考え方でコードがシンプルになり、保守が容易になるタスクはたくさんあります。

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

さて、どのように再帰呼び出しが動作するか検証してみましょう。そのためには関数の内部を見ていきます。

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

実行コンテキスト(execution context) は関数の実行に関する詳細を含む内部のデータ構造です。: 今はどの制御フローであるか、現在の変数、this の値(ここでは使いませんが)や、その他いくつかの内部データを持ちます。

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

関数がネスト呼び出しをした場合、次のようなことが起こります:

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

pow(2, 3) が呼ばれたとき、何が起きるのか見てみましょう。

pow(2, 3)

pow(2, 3) の呼び出しの始めでは、実行コンテキストは変数を格納します: x = 2, n= 3。実行フローは関数の 1 行目です。

我々はそれを次のようにスケッチできます:

  • Context: { x: 2, n: 3, at line 1 } pow(2, 3)

これは、関数が実行を開始したときです。条件 n == 1 は false なので、フローは if の2つ目の分岐(else)に続きます:

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

alert( pow(2, 3) );

変数は同じですが、行が変わっています。なので、コンテキストは次のようになります:

  • Context: { x: 2, n: 3, at line 5 } pow(2, 3)

x * pow(x, n - 1) を計算するためには、新しい引数 pow(2, 2) での pow のサブコールを作る必要があります。

pow(2, 2)

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

ここで、同じ関数 pow を呼びますが、まったく問題ありません。処理はすべての関数で同じです:

  1. 現在のコンテキストはスタックの先頭に “記憶” されます。
  2. サブコールをするための新しいコンテキストが作られます。
  3. サブコールが終わったとき、前のコンテキストがスタックから取り出され、実行が再開されます。

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

  • Context: { x: 2, n: 2, at line 1 } pow(2, 2)
  • Context: { x: 2, n: 3, at line 5 } pow(2, 3)

新しい現在の実行コンテキストが上(で太字のもの)で、以前に記憶されたコンテキストが下にあります。

サブコールが終わったとき、以前のコンテキストを再開するのは簡単です。なぜなら、変数と停止したコードの正確な位置を両方とも維持しているためです。

注意:

この図の中では、例では行にサブコールが1つしか無いので “行(line)” という言葉を使いましたが、通常1行のコードには pow(…) + pow(…) + somethingElse(…) のように複数のサブコールを含みます。

なので、実行は “サブコールの直後” に再開される、がより正確です。

pow(2, 1)

処理の繰り返し: 新しいサブコールが 5 行目で作られ、今は x=2, n=1 という引数です。

新しい実行コンテキストが作られ、前のものはスタックの先頭にプッシュされます。:

  • Context: { x: 2, n: 1, at line 1 } pow(2, 1)
  • Context: { x: 2, n: 2, at line 5 } pow(2, 2)
  • Context: { x: 2, n: 3, at line 5 } pow(2, 3)

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

The exit

pow(2, 1) の実行は、これまでとは異なり条件 n == 1 が真になります。従って if の最初の分岐に入ります:

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

それ以上ネストされた呼び出しはないので、関数は 2 を返して終わりです。

関数が終了したので、その実行コンテキストは不要となり、メモリから削除されます。そして、以前のコンテキストがスタックの先頭から復元されます。:

  • Context: { x: 2, n: 2, at line 5 } pow(2, 2)
  • Context: { x: 2, n: 3, at line 5 } pow(2, 3)

pow(2, 2) の実行が再開されます。これはサブコール pow(2, 1) の結果を持っているので、同様にx * pow(x, n - 1) の評価を完了することができ、4 を返します。

続いて、その前のコンテキストが復元されます:

  • Context: { x: 2, n: 3, at line 5 } pow(2, 3)

これが終了したとき、pow(2, 3) = 8 の結果を得ます。

このケースでの再帰の深さは 3 です。

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

メモリ要件に注意してください。コンテキストはメモリを必要とします。今回のケースでは、n のべき乗を行うためには、n より小さいすべての値に対して、コンテキストのためのメモリが必要です。

一方、ループベースのアルゴリズムはメモリを節約します:

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

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

  return result;
}

反復的な pow は処理の中で、 iresult が変化する1つのコンテキストを使います。そのメモリ要件は小さく、固定で n に依存しません。

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

…しかし、関数が条件によって異なる再帰サブコールを使用してその結果をマージするときや、分岐がより複雑な場合には書き直しは簡単ではないことがあります。また、最適化は不要であり、努力に値しないものである可能性があります。

再帰はより短いコードで書くことを可能とし、理解や保守をし易くします。 最適化はあらゆる場所で必要とされるわけではなく、大半は良いコードが必要です。そのために再帰は使用されています。

再帰的な横断

再帰のもう1つの優れた用途は、再帰的な探索です。

私たちは会社を持っていると想像してください。 スタッフの構造はオブジェクトで示すことができます:

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

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

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

言い換えると、会社は部署を持っています。

  • 部署はスタッフの配列を持っているかもしれません。例えば、sales 部門は2人の従業員がいます。John と Alice です。

  • もしくは、development は2つの枝(sitesinternals)を持っているように、部署はサブの部署に分割されるかもしれません。それらは各々のスタッフを持ちます。

  • サブの部署が成長したとき、サブのさらにサブ部署 (またはチーム) に分割される可能性もあります。

    例えば、将来 sites 部門が siteAsiteB のチームに分割されるかもしれません。そしてそれらは潜在的にさらに分割することができます。

では、全員の給料の合計を取得する関数が欲しいとしましょう。どのようにすればよいでしょう?

反復的なアプローチは簡単ではありません。なぜなら構造はシンプルではないためです。最初のアイデアは、第1レベルの所属のネストされたサブループをもつ companyfor をループを作ることです。しかし、次に sites のような 第2レベルの部門のスタッフを反復するためには、より多くのネストされたサブループが必要になります。…そして、将来現れるかもしれない第3レベルの部門のための別のサブループも必要ですか?またレベル3で停止するか、レベル4のループも作成する必要がありますか? 1つのオブジェクトを探索するために3〜4個のネストされたサブループをコード内に置くと、それはかなり醜いものになります。

再帰でトライしてみましょう。

上から分かるように、関数が合計するための部署を取得するとき、2つのケースがあります:

  1. 人の配列 を持つ “シンプルな” 部署の場合です。この場合は単純なループで給料を合計することができます。
  2. もしくは N 個のサブ部門を持つオブジェクト の場合です。この場合は、N 回の再帰呼び出しを行ってサブ部門の各合計を取得し、結果を結合します。

(1) は再帰の基底で、自明なケースです。

(2) は再帰ステップです。複雑なタスクはより小さい部門のためのサブタスクに分割されます。それらは次々に繰り返し分割するかもしれませんが、遅かれ早かれ分割は (1) で終わります。

このアルゴリズムは恐らくコードからさらに読みやすくなるでしょう:

let company = { // 同じオブジェクトです。簡略のため圧縮しています
  sales: [{name: 'John', salary: 1000}, {name: 'Alice', salary: 600 }],
  development: {
    sites: [{name: 'Peter', salary: 2000}, {name: 'Alex', salary: 1800 }],
    internals: [{name: 'Jack', salary: 1300}]
  }
};

// ジョブを行う関数
function sumSalaries(department) {
  if (Array.isArray(department)) { // case (1)
    return department.reduce((prev, current) => prev + current.salary, 0); // 配列の合計
  } else { // case (2)
    let sum = 0;
    for (let subdep of Object.values(department)) {
      sum += sumSalaries(subdep); // サブ部署への再帰呼び出し、結果を合計する
    }
    return sum;
  }
}

alert(sumSalaries(company)); // 6700

コードは(望んだように?)短く理解しやすくなりました。これが再帰の力です。また、これは任意のレベルのサブ部門のネスティングでも正しく動作します。

呼び出しの図式は次の通りです:

我々はその原理が容易に理解できます: オブジェクト {...} に対してはサブコールが作られ、配列 [...] は再帰ツリーの “葉” であり即座に結果を返します。

このコードでは、以前学んだスマートな機能を使っていることに留意してください:

  • 配列の合計を取得するために、チャプター 配列のメソッド で説明したメソッド arr.reduce を使用しています。
  • オブジェクトの値を反復するためにループfor(val of Object.values(obj)) を使用しています: Object.values は値の配列を返します。

再帰構造

再帰(再帰的に定義された)データ構造は、それ自身を部分的に複製する構造です。

私たちは、上の会社構造の例でちょうどそれを見ました。

会社の 部署 は:

  • 人の配列
  • もしくは 部署 を持つオブジェクト

web開発者にとっては、もっとよく知られている例があります: HTMLやXMLドキュメントです。

HTMLドキュメントでは、HTMLタグ には次の一覧が含まれています:

  • テキスト部分
  • HTML コメント
  • 他の HTMLタグ (これにはテキスト部分/コメントや他のタグなどが含まれています)

これは繰り返しになりますが、再帰的な定義です。

より深い理解のために、 もう1つ、いくつかのケースでは配列の代わりのより良い選択肢かもしれない “連結リスト” と呼ばれる再帰構造を学びましょう。

連結リスト(Linked list)

想像してください、我々が順序付けされたオブジェクトのリストを保存したいとします。

自然な選択肢は配列です:

let arr = [obj1, obj2, obj3];

…しかし、配列を使う場合には問題があります。 “要素の削除” と “要素の挿入” 操作はコストが高いです。例えば arr.unshift(obj) 操作は新しい obj のための場所を作るために、全ての要素の番号を振り直す必要があります。また、もし配列が大きい場合、それは時間がかかります。arr.shift() も同じです。

大量の番号の再割当てを必要としない唯一の構造変更は配列の末尾への操作です: arr.push/pop。従って、配列は大きなキューに対しては非常に遅くなる可能性があります。

あるいは、もしも本当に速い挿入/削除が必要であれば、連結リスト(linked list) と呼ばれる別のデータ構造を選択することもできます。

連結リスト要素 は次の要素をもつオブジェクトとして、再帰的に定義されます:

  • value.
  • 次の 連結リスト要素 または末尾の場合は null を参照する next プロパティ。

例:

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 };

// 新しい値をリストの前に追加する
list = { value: "new item", next: list };

間から値を取り除くには、その前の next を変更します:

list.next = list.next.next;

list.next1 を飛び越えて 2 という値になりました。値 1 は今やチェーンからは除外されています。もしもそれがどこにも保持されていない場合、自動的にメモリから削除されます。

配列とは違って、大量の番号の再割り当てはなく、要素を簡単に組み替えることができます。

当然ながら、リストは常に配列よりも優れているとは限りません。そうでなければ皆リストだけを使うでしょう。

主な欠点は、番号では簡単に要素にアクセスできないことです。配列では簡単です( arr[n] で直接参照します)が、リストではアイテムの最初から始めてN個目の要素を取得するために、Nnext を行う必要があります。

…でも、常にこのような操作が必要とは限りません。例えば、キュー(queue)や デック(deque) が必要なときです。これらは両端から要素を非常に高速に追加/削除できる順序付けられた構造です。

リストは拡張できます:

  • next に加えて prev プロパティも付け加えることで、前の要素を参照するために簡単に戻れるようにすることができます。
  • リストの最後の要素を参照する tail と呼ばれる変数を追加することもできます(末尾から要素を追加/削除するときに更新します)。
  • …データ構造はニーズに応じて異なります。

サマリ

用語:

  • 再帰 は “自己呼び出し” 関数を意味するプログラミングの用語です。このような関数を使用して、特定のタスクを簡潔で美しい方法で解決することができます。

    関数が自身を呼び出すとき、それは 再帰ステップ と呼ばれます。 再帰の 基底 は、関数がそれ以上の呼び出しを行わないようにタスクを単純化する関数の引数です。

  • 再帰的な定義(recursively-defined) データ構造は自身を使って定義できるデータ構造です。

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

    list = { value, next -> list }

    このチャプターにあったHTML要素や部署のようなツリーもまた、もちろん再帰的です: それらは分岐し、各分岐は別の分岐をもつことができます。

    sumSalary の例で見たように、再帰関数を使ってそれらを見て回ることができます。

どんな再帰関数も反復的なものに書き直すことができます。そして、時には最適化を行う必要があります。しかし、多くのタスクでは、再帰的な解決策は十分速く、書きやすく、保守が簡単です。

タスク

重要性: 5

数値の合計 1 + 2 + ... + n を計算する関数 sumTo(n) を書いてください。

例:

sumTo(1) = 1
sumTo(2) = 2 + 1 = 3
sumTo(3) = 3 + 2 + 1 = 6
sumTo(4) = 4 + 3 + 2 + 1 = 10
...
sumTo(100) = 100 + 99 + ... + 2 + 1 = 5050

解答のバリアントを3つ作ってください:

  1. for ループを使ってください。
  2. 再帰を使ってください。n > 1 に対して sumTo(n) = n + sumTo(n-1) となるような。
  3. 等差数列 の式を使ってください。

結果の例です:

function sumTo(n) { /*... your code ... */ }

alert( sumTo(100) ); // 5050

P.S. どの解決策が最も速いでしょう?そして遅いものはどれ?なぜでしょう?

P.P.S. 再帰を使って sumTo(100000) を数えることはできますか?

ループを使った解決策です:

function sumTo(n) {
  let sum = 0;
  for (let i = 1; i <= n; i++) {
    sum += i;
  }
  return sum;
}

alert( sumTo(100) );

再帰を使った解決策です:

function sumTo(n) {
  if (n == 1) return 1;
  return n + sumTo(n - 1);
}

alert( sumTo(100) );

公式: sumTo(n) = n*(n+1)/2 を使った解決策です:

function sumTo(n) {
  return n * (n + 1) / 2;
}

alert( sumTo(100) );

P.S. 当然のことながら、この式は最速の解法です。任意の数 n に対して3つの演算しか使用しません。数学は助けます!

ループのバリアントは速度の点では2番目です。再帰とループのバリアント共に同じ数を合計していますが、再帰にはネストされた呼び出しと実行スタック管理が含まれます。それもまたリソースを取るため、より遅くなります。

P.P.S この規格は、「テールコール(末尾呼び出し)」最適化について説明しています。もし再帰呼び出しが関数の中の最後のものである場合(上の sumTo のように)、外部の関数は実行を再開する必要はなく、その実行コンテキストを覚えておく必要はありません。その場合であれば、sumTo(100000) はカウント可能です。しかし、もしあなたのJavaScriptエンジンがそれをサポートしていない場合は最大スタックサイズを超えたというエラーが発生します。これは、通常、スタックサイズの合計に制限があるためです。

重要性: 4

自然数の 階乗 は 数値に "数値 - 1" を掛け、次に "数値 - 2" を掛け、… 1 まで行います。n の階乗は n! と表されます。

階乗の定義はこのように書くことができます:

n! = n * (n - 1) * (n - 2) * ...*1

異なる n の階乗の値は次のようになります:

1! = 1
2! = 2 * 1 = 2
3! = 3 * 2 * 1 = 6
4! = 4 * 3 * 2 * 1 = 24
5! = 5 * 4 * 3 * 2 * 1 = 120

このタスクは再帰呼び出しを使って n! の計算をする関数 factorial(n) を書くことです。

alert( factorial(5) ); // 120

P.S. ヒント: n!n * (n-1)! と書くことができます。例えば: 3! = 3*2! = 3*2*1! = 6

定義によると、階乗 n!n * (n-1)! と書くことができます。

つまり、factorial(n) の結果は nfactorial(n-1) の結果で掛けたものとして計算することができます。

function factorial(n) {
  return (n != 1) ? n * factorial(n - 1) : 1;
}

alert( factorial(5) ); // 120

再帰のベース値は 1 です。ここではベースを 0 にすることもできます。それほど問題ではありませんが、再帰的なステップが1回増えます:

function factorial(n) {
  return n ? n * factorial(n - 1) : 1;
}

alert( factorial(5) ); // 120
重要性: 5

フィボナッチ数(Fibonacci numbers)の配列には Fn = Fn-1 + Fn-2 という式があります。つまり、次の数字は前の2つの数字の合計です。

最初の2角数値は 1 で、次に 2(1+1)、次は 3(1+2), 5(2+3), と続きます: 1, 1, 2, 3, 5, 8, 13, 21....

フィボナッチ数は 黄金比や私たちの周りの多くの自然現象に関連しています。

n-th のフィボナッチ数を返す関数 fib(n) を書いてください。

動作例:

function fib(n) { /* your code */ }

alert(fib(3)); // 2
alert(fib(7)); // 13
alert(fib(77)); // 5527939700884757

P.S. 関数は速くあるべきです。fib(77) の呼び出しは1秒より小さくある必要があります。

ここでトライする最初の解法は再帰的なものです。

フィボナッチ数は定義上再帰的です:

function fib(n) {
  return n <= 1 ? n : fib(n - 1) + fib(n - 2);
}

alert( fib(3) ); // 2
alert( fib(7) ); // 13
// fib(77); // とても遅いでしょう!

…しかし、n が大きな値だととても遅いです。例えば fib(77) はしばらくすべてのCPUリソースを食べるのでエンジンがハングアップするかもしれません。

それは、関数があまりにも多くのサブコールを作るためです。同じ値が何度も何度も再評価されます。

例えば、fib(5) に対する計算の一部を見てみましょう:

...
fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
...

ここでは、 fib(3) の値が fib(5)fib(4) 両方で必要とされていることが分かります。なので fib(3) は2回完全に独立して呼び出され、評価されます。

これは完全な再帰ツリーです:

fib(3) が 2回評価され、fib(2) は3回評価されることが明確にわかります。計算の総量は n よりも遥かに速く大きくなり、n=77 でさえ巨大になります。

私たちは、すでに評価された値を覚えておくことでそれを最適化することができます: もし fib(3) が一度呼ばれると、以降の将来の計算では単にそれを再利用させます。

別のバリアントとしては、再帰をやめ、全く異なるループベースのアルゴリズムを使うことです。

n から小さい値へ進む代わりに、12 から開始するループを作ることができます。それらの合計として fib(3) を取得し、次に2つ前の値の合計として fib(4) を、次に fib(5) と必要な値を取得するまで上に上がっていきます。各ステップでは以前の2つの値を覚えておくだけで済みます。

ここでは、新しいアルゴリズムのステップの詳細を示します。

スタート:

// a = fib(1), b = fib(2), これらの値は定義のより 1 です
let a = 1, b = 1;

// これらの合計として get c = fib(3)
let c = a + b;

/* 今 fib(1), fib(2), fib(3) を持っています
a  b  c
1, 1, 2
*/

今、fib(4) = fib(2) + fib(3) を取得したいとします。

変数をシフトさせましょう: a,bfib(2),fib(3) を取り、c はそれらの合計です:

a = b; // 今 a = fib(2)
b = c; // 今 b = fib(3)
c = a + b; // c = fib(4)

/* 今私たちが持っている数列:
   a  b  c
1, 1, 2, 3
*/

次のステップは別の数列を与えます:

a = b; // 今 a = fib(3)
b = c; // 今 b = fib(4)
c = a + b; // c = fib(5)

/* 今、数列は次の通り:
      a  b  c
1, 1, 2, 3, 5
*/

…として必要な値まで繰り返します。これは再帰よりも遥かに速く、重複する計算を起こしません。

完全なコードです:

function fib(n) {
  let a = 1;
  let b = 1;
  for (let i = 3; i <= n; i++) {
    let c = a + b;
    a = b;
    b = c;
  }
  return b;
}

alert( fib(3) ); // 2
alert( fib(7) ); // 13
alert( fib(77) ); // 5527939700884757

ループは i=3 でスタートします。なぜなら、最初と2番目の数列値は変数 a=1, b=1 でハードコードされているためです。

このアプローチは動的計画法(dynamic programming bottom-up)と呼ばれます。

重要性: 5

単一の連結リスト(チャプター 再帰とスタック での説明の通り)を持っています。:

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

リストのアイテムを1つずつ出力する関数 printList(list) を書いてください。

解法を2つのバリアントで作成してください: ループを使った方法と再帰を利用した方法。

ベターなのは?: 再帰 or 再帰なし?

ループベースの解法

ループベースの解法のバリアントです:

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

function printList(list) {
  let tmp = list;

  while (tmp) {
    alert(tmp.value);
    tmp = tmp.next;
  }

}

printList(list);

リストを歩くために一時的な変数 tmp を使用していることに留意してください。技術的には、代わりに関数パラメータ list を使うことができます。:

function printList(list) {

  while(list) {
    alert(list.value);
    list = list.next;
  }

}

…しかし、それは賢くありません。将来、リストに何かをするよう、関数を拡張する必要があるかもしれません。もし list を変えると、このような能力を失います。

良い変数名について言うと、list はここではリスト自身です。その最初の要素です。そして、それはそのままでいるべきです。それは明らかで信頼できるものです。

一方、tmp の役割は for ループでの i のように、排他的なリストのトラバーサルです。

再帰的な解法

printList(list) の再帰的なバリアントはシンプルなロジックに従います: リストを出力するために、現在の要素 list を出力し、list.next に対して同じことをします。:

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

function printList(list) {

  alert(list.value); // 現在のアイテムを出力

  if (list.next) {
    printList(list.next); // 残ったリストに対して同じことをする
  }

}

printList(list);

さて、何がベターでしょう?

技術的には、ループはより効率的です。これらの2つのバリアントは同じことをしますが、ループは入れ子の関数呼び出しのためのリソースを消費しません。

別の観点では、再帰のバリアントはより短く、理解しやすい場合があります。

重要性: 5

前のタスク 単一連結リストを出力する からの単一の連結リストを逆順で出力してください。

2つの解法を作ってください。: ループと再帰を使った方法です。

再帰を利用した方法

ここでは、再帰ロジックは少しトリッキーです。

最初に残りのリストを出力し、その後 現在の内容を出力する必要があります:

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

function printReverseList(list) {

  if (list.next) {
    printReverseList(list.next);
  }

  alert(list.value);
}

printReverseList(list);

ループを使う

ループのバリアントもまた直接出力よりも少し複雑です。

我々の list で最後の値を取得する方法はありません。また、 “戻る” こともできません。

従って、できることは直接の並びでアイテムを調べて、それらを配列に覚えます。そして逆順で覚えていることを出力していきます。:

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

function printReverseList(list) {
  let arr = [];
  let tmp = list;

  while (tmp) {
    arr.push(tmp.value);
    tmp = tmp.next;
  }

  for (let i = arr.length - 1; i >= 0; i--) {
    alert( arr[i] );
  }
}

printReverseList(list);

再帰的な解法は、実際には全くに同じであることに留意してください。: リストに沿って、(実行コンテキストスタック内の)ネストされた呼び出しのチェーン内の項目を覚え、それらを出力します。

チュートリアルマップ