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

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

あなたが初心者のプログラマーでないなら、それはおそらくおなじみなので、このチャプターをスキップしても問題ありません。

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

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

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 エンジンによって制限されています。10000 は確実で、エンジンによってはより多くの値が可能です。しかし、100000 は大多数の制限を恐らく超えます。これを緩和する自動最適化があります(“末尾再帰”)が、どこでもサポートされているわけではなく、単純なケースでのみ機能します。

それは再帰の適用を制限しますが、依然として非常に広範囲に使われています。再帰的な考え方はよりコードをシンプルにし、維持しやすくするための多くのメリットがあります。

実行スタック

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

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

実行コンテキスト(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)

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

サブコールが終わったとき、以前のコンテキストを再開するのは簡単です。なぜなら、変数と停止したコードの正確な位置を両方とも維持しているためです。ここの絵の中では、“行(line)” という言葉を使いましたが、もちろんそれはより精密です。

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 の値より小さいすべてにの値に対して、n 個のコンテキストのためのメモリが必要です。

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

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

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

  return result;
}

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

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

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

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

再帰的な横断

再帰の別の優れた応用は、再帰的な探索である。

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

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

ここでは、複数のオブジェクトがあり、それぞれが 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) が必用なときです – 両端から要素を非常に高速に追加/削除できる順序付けられた構造です。

リストの最後の要素を追跡するために 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);

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

チュートリアルマップ

コメント

コメントをする前に読んでください…
  • 自由に記事への追加や質問を投稿をしたり、それらに回答してください。
  • 数語のコードを挿入するには、<code> タグを使ってください。複数行の場合は <pre> を、10行を超える場合にはサンドボックスを使ってください(plnkr, JSBin, codepen…)。
  • 記事の中で理解できないことがあれば、詳しく説明してください。