関数に戻って、さらに詳しく調べてみましょう。
最初のトピックは再帰です。
プログラミングに慣れていない場合は、おそらく馴染みのあるものなので、この章を飛ばしても問題ありません。
再帰は、タスクが同じ種類のより単純な複数のタスクに自然に分割できる状況で役立つプログラミング パターンです。または、タスクを簡単なアクションと、同じタスクのより単純なバリエーションに単純化できる場合。または、すぐに説明するように、特定のデータ構造を処理するためです。
関数がタスクを解決するとき、その過程で他の多くの関数を呼び出すことができます。この一部のケースは、関数がそれ自体を呼び出す場合です。それは再帰と呼ばれます。
まずは簡単なこととして、 x nの自然乗する関数pow(x, n)を書いてみましょう。言い換えれば、 xそれ自身でn回乗算します。
pow(2, 2) = 4 pow(2, 3) = 8 pow(2, 4) = 16
実装するには 2 つの方法があります。
反復的思考: forループ:
関数 pow(x, n) {
結果 = 1 とします。
// ループ内で結果を x で n 回乗算します
for (let i = 0; i < n; i++) {
結果 *= x;
}
結果を返します。
}
アラート( pow(2, 3) ); // 8再帰的思考: タスクを単純化し、self を呼び出します。
関数 pow(x, n) {
if (n == 1) {
x を返します。
} それ以外 {
return x * pow(x, n - 1);
}
}
アラート( pow(2, 3) ); // 8再帰的バリアントが根本的にどのように異なるかに注意してください。
pow(x, n)が呼び出されると、実行は 2 つの分岐に分割されます。
n==1 = x の場合
/
pow(x, n) =
else = x * pow(x, n - 1) n == 1の場合、すべては自明です。これは、 pow(x, 1)がxに等しいという明白な結果を即座に生成するため、再帰のベースと呼ばれます。
それ以外の場合は、 pow(x, n) x * pow(x, n - 1)として表すことができます。数学では、 x n = x * x n-1と書きます。これは再帰的ステップと呼ばれます。タスクをより単純なアクション ( xによる乗算) と、同じタスクのより単純な呼び出し ( nが小さいpow ) に変換します。次のステップでは、 n 1達するまでさらに単純化していきます。
pow n == 1になるまで再帰的に自分自身を呼び出すとも言えます。
たとえば、 pow(2, 4)を計算するには、再帰的バリアントは次の手順を実行します。
pow(2, 4) = 2 * pow(2, 3)
pow(2, 3) = 2 * pow(2, 2)
pow(2, 2) = 2 * pow(2, 1)
pow(2, 1) = 2
したがって、再帰によって関数呼び出しがより単純なものに縮小され、さらに結果が明らかになるまでさらに単純に縮小されます。
通常、再帰は短くなります
再帰的解決策は通常、反復的解決策よりも短くなります。
ここで、条件演算子?を使用して同じ内容を書き直すことができます。 ifの代わりにpow(x, n)より簡潔に、しかも非常に読みやすくするために次のようにします。
関数 pow(x, n) {
戻り値 (n == 1) ? x : (x * pow(x, n - 1));
}ネストされた呼び出しの最大数 (最初の呼び出しを含む) は、再帰の深さと呼ばれます。私たちの場合、それは正確にnになります。
再帰の最大の深さは JavaScript エンジンによって制限されます。 10000 であることは信頼できます。一部のエンジンではそれ以上の値が許容されますが、おそらくほとんどのエンジンでは 100000 は制限外です。これを軽減するのに役立つ自動最適化 (「テール コール最適化」) がありますが、これらはまだどこでもサポートされているわけではなく、単純な場合にのみ機能します。
これにより再帰の適用が制限されますが、依然として非常に広い範囲に適用されます。再帰的な考え方によってコードが単純になり、保守が容易になるタスクは数多くあります。
次に、再帰呼び出しがどのように機能するかを調べてみましょう。そのために、関数の内部を見ていきます。
実行中の関数の実行プロセスに関する情報は、その実行コンテキストに保存されます。
実行コンテキストは、関数の実行に関する詳細を含む内部データ構造です。制御フローの現在の場所、現在の変数、 thisの値 (ここでは使用しません)、およびその他のいくつかの内部詳細が含まれます。
1 つの関数呼び出しには、関連付けられた実行コンテキストが 1 つだけあります。
関数がネストされた呼び出しを行うと、次のことが起こります。
現在の機能は一時停止されています。
これに関連付けられた実行コンテキストは、実行コンテキスト スタックと呼ばれる特別なデータ構造に記憶されます。
ネストされた呼び出しが実行されます。
終了後、古い実行コンテキストがスタックから取得され、外部関数が停止した場所から再開されます。
pow(2, 3)呼び出し中に何が起こるかを見てみましょう。
pow(2, 3)呼び出しの開始時に、実行コンテキストは変数x = 2, n = 3を格納します。実行フローは関数の1行目にあります。
次のようにスケッチできます。
コンテキスト: { x: 2, n: 3、1 行目 } pow(2, 3)
その時点で関数の実行が開始されます。条件n == 1は偽であるため、フローはifの 2 番目の分岐に進みます。
関数 pow(x, n) {
if (n == 1) {
x を返します。
} それ以外 {
return x * pow(x, n - 1);
}
}
アラート( pow(2, 3) );変数は同じですが、行が変更されているため、コンテキストは次のようになります。
コンテキスト: { x: 2, n: 3、5 行目 } pow(2, 3)
x * pow(x, n - 1)を計算するには、新しい引数pow(2, 2)を使用してpowのサブコールを作成する必要があります。
ネストされた呼び出しを行うために、JavaScript は現在の実行コンテキストを実行コンテキスト スタックに記憶します。
ここでは同じ関数をpow呼びますが、それはまったく問題ではありません。このプロセスはすべての関数で同じです。
現在のコンテキストはスタックの最上位に「記憶」されます。
サブコール用に新しいコンテキストが作成されます。
サブコールが終了すると、前のコンテキストがスタックからポップされ、実行が続行されます。
サブコールpow(2, 2)を入力したときのコンテキスト スタックは次のとおりです。
コンテキスト: { x: 2, n: 2、1 行目 } pow(2, 2)
コンテキスト: { x: 2, n: 3、5 行目 } pow(2, 3)
新しい現在の実行コンテキストが一番上 (太字) で、以前に記憶されているコンテキストがその下にあります。
サブコールが終了すると、変数と停止したコードの正確な場所の両方が保持されるため、以前のコンテキストを簡単に再開できます。
ご注意ください：
この例では、行にサブコールが 1 つしかないため、この図では「行」という単語を使用していますが、一般に、コードの 1 行には、 pow(…) + pow(…) + somethingElse(…)のように複数のサブコールが含まれる場合があります。 。
したがって、実行は「サブコールの直後に」再開されると言ったほうが正確です。
このプロセスが繰り返されます。新しいサブコールが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)
現在、古いコンテキストが 2 つあり、現在pow(2, 1)で実行されているコンテキストが 1 つあります。
pow(2, 1)の実行中は、以前とは異なり、条件n == 1が真であるため、 ifの最初の分岐が機能します。
関数 pow(x, n) {
if (n == 1) {
x を返します。
} それ以外 {
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のコンテキストのメモリが必要です。
ループベースのアルゴリズムはメモリをより節約します。
関数 pow(x, n) {
結果 = 1 とします。
for (let i = 0; i < n; i++) {
結果 *= x;
}
結果を返します。
}反復的なpow iとresult変更する単一のコンテキストを使用してプロセスを実行します。そのメモリ要件は小さく、固定されており、 nには依存しません。
あらゆる再帰はループとして書き直すことができます。通常、ループのバリアントをより効果的にすることができます。
…しかし、特に関数が条件に応じて異なる再帰サブコールを使用し、その結果をマージする場合や、分岐がより複雑な場合には、書き換えが重要になることがあります。そして、最適化は不必要であり、努力する価値がまったくない可能性があります。
再帰によりコードが短くなり、理解しやすく、サポートしやすくなります。最適化はあらゆる場所で必要なわけではありません。ほとんどの場合、適切なコードが必要なので、最適化が使用されます。
再帰のもう 1 つの優れた応用は、再帰的走査です。
想像してみてください。私たちには会社があります。譜表構造はオブジェクトとして表すことができます。
会社 = { にしましょう
販売: [{
名前：「ジョン」、
給与: 1000
}、{
名前：「アリス」、
給与: 1600
}]、
発達： {
サイト: [{
名前：「ピーター」、
給与: 2000
}、{
名前：「アレックス」、
給与: 1800
}]、
内部: [{
名前：「ジャック」、
給与: 1300
}]
}
};言い換えれば、会社には部門があります。
部門にはさまざまなスタッフがいる場合があります。たとえば、 sales部門にはジョンとアリスという 2 人の従業員がいます。
あるいは、 development部門にsitesとinternals 2 つの部門があるように、部門がサブ部門に分割される場合もあります。それぞれに独自のスタッフがいます。
また、サブ部門が成長すると、サブ部門 (またはチーム) に分割される可能性もあります。
たとえば、将来的にsites部門はsiteAとsiteBのチームに分割される可能性があります。そして、潜在的にはさらに分裂する可能性があります。それは写真にはありませんが、心に留めておいてください。
ここで、すべての給与の合計を取得する関数が必要だとします。どうすればそれができるでしょうか？
構造が単純ではないため、反復的なアプローチは簡単ではありません。最初のアイデアは、第 1 レベルの部門を越えるネストされたサブループを持つcompany越えるforループを作成することかもしれません。しかし、 sitesなどの第 2 レベルの部門のスタッフを反復処理するには、さらに入れ子になったサブループが必要です。そして、将来出現する可能性のある第 3 レベルの部門のサブループ内に別のサブループが必要になるでしょうか?単一のオブジェクトを走査するためにコード内に 3 ～ 4 個のネストされたサブループを入れると、かなり見苦しくなります。
再帰を試してみましょう。
ご覧のとおり、関数が部門の合計を取得する場合、考えられるケースは 2 つあります。
それが多数の人々を抱える「単純な」部門である場合、単純なループで給与を合計できます。
または、 Nサブ部門を持つオブジェクトである場合、 Nの再帰呼び出しを行って各サブ部門の合計を取得し、結果を結合することができます。
1 番目のケースは再帰の基礎であり、配列を取得するときの自明なケースです。
オブジェクトを取得する 2 番目のケースは再帰的なステップです。複雑なタスクは、より小さな部門のサブタスクに分割されます。彼らは再び分裂する可能性がありますが、遅かれ早かれ分裂は(1)で終了します。
アルゴリズムは、おそらくコードから読み取る方がさらに簡単です。
let company = { // 同じオブジェクト、簡潔にするために圧縮
売上: [{名前: 'ジョン'、給与: 1000}、{名前: 'アリス'、給与: 1600 }]、
発達： {
サイト: [{名前: 'ピーター'、給与: 2000}、{名前: 'アレックス'、給与: 1800 }]、
内部事情: [{名前: 'ジャック'、給与: 1300}]
}
};
// ジョブを実行する関数
関数 sumSalaries(部門) {
if (Array.isArray(デパートメント)) { // ケース (1)
return 部門.reduce((prev, current) => prev + current.salary, 0); // 配列の合計を計算します
} else { // ケース (2)
合計 = 0 とします。
for (Object.values(Department) の subdep を許可) {
合計 += 合計給与(サブデプ); // サブ部門を再帰的に呼び出し、結果を合計します
}
合計を返します。
}
}
アラート(合計給与(会社)); // 7700コードは短くて理解しやすいです (うまくいけば?)。それが再帰の力です。また、どのレベルのサブ部門のネストにも機能します。
呼び出しの図は次のとおりです。
原理は簡単にわかります。オブジェクト{...}に対してサブコールが行われ、配列[...]は再帰ツリーの「葉」であり、即時に結果が得られます。
このコードでは、以前に説明したスマートな機能が使用されていることに注意してください。
メソッドarr.reduce配列の合計を取得する配列メソッドの章で説明されています。
for(val of Object.values(obj))ループしてオブジェクト値を反復します。Object.values Object.valuesそれらの配列を返します。
再帰的 (再帰的に定義された) データ構造は、それ自体を部分的に複製する構造です。
上の会社構造の例でそれを見てきました。
会社の部門は次のとおりです。
人の配列のいずれかです。
または、部門を含むオブジェクト。
Web 開発者にとっては、HTML ドキュメントと XML ドキュメントというよく知られた例があります。
HTML ドキュメントでは、 HTML タグに次のリストが含まれる場合があります。
テキスト部分。
HTML コメント。
他のHTML タグ(テキスト部分/コメント、または他のタグなどが含まれる場合があります)。
これも再帰的な定義です。
よりよく理解するために、場合によっては配列のより良い代替となる可能性がある「リンク リスト」という名前のもう 1 つの再帰構造について説明します。
オブジェクトの順序付きリストを保存したいと想像してください。
自然な選択は配列です。
arr = [obj1, obj2, obj3]; にします。
…しかし、配列には問題があります。 「要素の削除」および「要素の挿入」操作は負荷が高くなります。たとえば、 arr.unshift(obj)操作では、新しいobj用のスペースを確保するためにすべての要素の番号を付け直す必要があり、配列が大きい場合は時間がかかります。 arr.shift()も同様です。
一括再番号付けを必要としない唯一の構造変更は、配列の末尾を操作するものです: arr.push/pop 。したがって、最初から作業する必要がある場合、大きなキューでは配列が非常に遅くなる可能性があります。
あるいは、本当に高速な挿入/削除が必要な場合は、リンク リストと呼ばれる別のデータ構造を選択できます。
リンクされたリスト要素は、次のオブジェクトとして再帰的に定義されます。
value 。
次のリンクされたリスト要素を参照するnextプロパティ、またはそれが終わりの場合はnull 。
例えば：
let リスト = {
値: 1、
次： {
値: 2、
次： {
値: 3、
次： {
値: 4、
次へ: null
}
}
}
};リストのグラフ表示:
作成用の代替コード:
let list = { 値: 1 };
list.next = { 値: 2 };
list.next.next = { 値: 3 };
list.next.next.next = { 値: 4 };
list.next.next.next.next = null;ここでは、複数のオブジェクトがあり、それぞれがvalueを持ち、 next隣接するオブジェクトを指していることがさらに明確にわかります。 list変数はチェーン内の最初のオブジェクトであるため、そこからnextポインターをたどると、任意の要素に到達できます。
リストは簡単に複数の部分に分割し、後で結合し直すことができます。
SecondList = list.next.next; にしましょう。 list.next.next = null;
参加するには:
list.next.next = 秒リスト;
そして確かに、どの場所でもアイテムを挿入したり削除したりすることができます。
たとえば、新しい値を先頭に追加するには、リストの先頭を更新する必要があります。
let list = { 値: 1 };
list.next = { 値: 2 };
list.next.next = { 値: 3 };
list.next.next.next = { 値: 4 };
// 新しい値をリストの先頭に追加します
list = { 値: "新しい項目"、次: リスト }; 中間の値を削除するには、前の値のnext変更します。
リスト.ネクスト = リスト.ネクスト.ネクスト;
list.next 1から value 2にジャンプさせました。値1はチェーンから除外されます。他の場所に保存されていない場合は、メモリから自動的に削除されます。
配列とは異なり、大量の再番号付けはなく、要素を簡単に再配置できます。
当然のことながら、リストが常に配列よりも優れているわけではありません。そうでなければ、誰もがリストだけを使用するでしょう。
主な欠点は、番号によって要素に簡単にアクセスできないことです。配列の場合は簡単です。arr arr[n]は直接参照です。ただし、リストでは、最初の項目から開始して、N 番目の要素を取得するためにnext項目にN回移動する必要があります。
…しかし、必ずしもそのような操作が必要なわけではありません。たとえば、キューやデキューが必要な場合、これは両端からの要素の非常に高速な追加/削除を可能にしなければならない順序付けられた構造ですが、その中間へのアクセスは必要ありません。
リストは次のように拡張できます。
nextに加えてprevプロパティを追加して、前の要素を参照し、簡単に戻ることができます。
リストの最後の要素を参照するtailという名前の変数を追加することもできます (最後に要素を追加または削除するときに変数を更新します)。
…データ構造はニーズに応じて異なる場合があります。
条項：
再帰とは、それ自体から関数を呼び出すことを意味するプログラミング用語です。再帰関数を使用すると、エレガントな方法でタスクを解決できます。
関数がそれ自体を呼び出すとき、それは再帰ステップと呼ばれます。再帰の基礎は、関数がそれ以上呼び出しを行わないようにタスクを単純にする関数の引数です。
再帰的に定義されたデータ構造は、それ自体を使用して定義できるデータ構造です。
たとえば、リンクされたリストは、リスト (または null) を参照するオブジェクトから構成されるデータ構造として定義できます。
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 つのソリューションのバリエーションを作成します。
for ループを使用します。
再帰を使用すると、 n > 1の場合sumTo(n) = n + sumTo(n-1)になります。
等差数列公式を使用します。
結果の例:
function sumTo(n) { /*... コード ... */ }
アラート( sumTo(100) ); // 5050PS どのソリューション バリアントが最も速いですか?一番遅い？なぜ？
PPS 再帰を使用してsumTo(100000)をカウントできますか?
ループを使用した解決策:
関数 sumTo(n) {
合計 = 0 とします。
for (let i = 1; i <= n; i++) {
合計 += i;
}
合計を返します。
}
アラート( sumTo(100) );再帰を使用した解決策:
関数 sumTo(n) {
if (n == 1) は 1 を返します。
n + sumTo(n - 1) を返します。
}
アラート( sumTo(100) );式を使用した解: sumTo(n) = n*(n+1)/2 :
関数 sumTo(n) {
n * (n + 1) / 2 を返します。
}
アラート( sumTo(100) ); PS 当然のことながら、この公式が最速の解決策です。任意の数値nに対して 3 つの演算のみを使用します。数学は役に立ちます!
ループ バリアントは速度の点で 2 番目です。再帰的バリアントとループバリアントの両方で、同じ数値を合計します。ただし、再帰にはネストされた呼び出しと実行スタック管理が含まれます。これにはリソースも必要になるため、速度が遅くなります。
PPS 一部のエンジンは「末尾呼び出し」最適化をサポートしています。再帰呼び出しが関数の最後の呼び出しで、他の計算が実行されない場合、外側の関数は実行を再開する必要がないため、エンジンは実行を再開する必要がありません。その実行コンテキストを覚えておいてください。これにより、記憶への負担が軽減されます。ただし、JavaScript エンジンが末尾呼び出しの最適化をサポートしていない場合 (ほとんどのエンジンはサポートしていません)、通常は合計スタック サイズに制限があるため、「最大スタック サイズを超えました」というエラーが発生します。
重要度: 4
自然数の階乗は、 "number minus one"を乗算し、次に"number minus two"を乗算して1になるまで続きます。 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)を書くことです。再帰呼び出しを使用します。
アラート(factorial(5) ); // 120
PS ヒント: n! n * (n-1)!例: 3! = 3*2! = 3*2*1! = 6
定義上、階乗n! n * (n-1)! 。
つまり、 factorial(n)の結果は、 nとfactorial(n-1)の結果の積として計算できます。そして、 n-1の呼び出しは、 1になるまで再帰的に下降することができます。
関数階乗(n) {
return (n != 1) ? n * 階乗(n - 1) : 1;
}
アラート(factorial(5) ); // 120再帰の基礎は値1です。ここで0基準にすることもできますが、これはあまり重要ではありませんが、再帰的なステップが 1 つ追加されます。
関数階乗(n) {
nを返しますか？ n * 階乗(n - 1) : 1;
}
アラート(factorial(5) ); // 120重要度: 5
フィボナッチ数列の式はF n = F n-1 + F n-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) { /* コード */ }
アラート(fib(3)); // 2
アラート(fib(7)); // 13
アラート(fib(77)); // 5527939700884757 PS 関数は高速である必要があります。 fib(77)の呼び出しにはほんの 1 秒もかかりません。
ここで試せる最初の解決策は再帰的解決策です。
フィボナッチ数は定義上再帰的です。
関数 fib(n) {
n <= 1 を返しますか? n : fib(n - 1) + fib(n - 2);
}
アラート( fib(3) ); // 2
アラート( 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)の値が一度計算されれば、それを将来の計算で再利用することができます。
もう 1 つの変形は、再帰を放棄し、まったく異なるループベースのアルゴリズムを使用することです。
nからより低い値に進む代わりに、 1と2から開始して、それらの合計としてfib(3)を取得し、次に前の 2 つの値の合計としてfib(4)を取得し、次にfib(5)取得するループを作成できます。必要な値に達するまで、どんどん上がっていきます。各ステップで、前の 2 つの値を覚えておくだけで済みます。
新しいアルゴリズムの手順を詳しく説明します。
始まり:
// a = fib(1)、b = fib(2)、これらの値は定義により 1 a = 1、b = 1 とします。 // c = fib(3) を合計として取得します c = a + b とします。 /* これで fib(1)、fib(2)、fib(3) ができました。 a b c 1、1、2 */
ここで、 fib(4) = fib(2) + fib(3)を取得したいとします。
変数をシフトしましょう。 a,b fib(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)
/* 現在のシーケンスは (もう 1 つの数字) です:
a b c
1、1、2、3、5
*/…必要な値が得られるまでこれを繰り返します。これは再帰よりもはるかに高速であり、重複した計算は必要ありません。
完全なコード:
関数 fib(n) {
a = 1 とします。
b = 1 とします。
for (let i = 3; i <= n; i++) {
c = a + b とします。
a = b;
b = c;
}
bを返します。
}
アラート( fib(3) ); // 2
アラート( fib(7) ); // 13
アラート( fib(77) ); // 5527939700884757最初と 2 番目のシーケンス値は変数a=1 、 b=1にハードコードされているため、ループはi=3から始まります。
このアプローチは、動的プログラミングのボトムアップと呼ばれます。
重要度: 5
(「再帰とスタック」の章で説明されているように) 単一リンクのリストがあるとします。
let リスト = {
値: 1、
次： {
値: 2、
次： {
値: 3、
次： {
値: 4、
次へ: null
}
}
}
};リスト項目を 1 つずつ出力する関数printList(list)を作成します。
ループを使用する方法と再帰を使用する方法の 2 つの解決策を作成します。
再帰ありとなしではどちらが良いでしょうか?
ループベースのソリューションのバリエーション:
let リスト = {
値: 1、
次： {
値: 2、
次： {
値: 3、
次： {
値: 4、
次へ: null
}
}
}
};
関数 printList(リスト) {
tmp = リストとします。
while (tmp) {
アラート(tmp.value);
tmp = tmp.next;
}
}
printList(リスト);リスト内を移動するには一時変数tmp使用することに注意してください。技術的には、代わりに関数パラメータlistを使用できます。
関数 printList(リスト) {
while(リスト) {
アラート(リスト.値);
リスト = リスト.次へ;
}
} …しかし、それは賢明ではありません。将来的には、関数を拡張したり、リストに対して別のことを行う必要があるかもしれません。 list変更すると、そのような機能は失われます。
適切な変数名について言えば、ここにあるlistはリストそのものです。その最初の要素。そしてそれはそのままであるべきです。それは明確で信頼できることです。
逆に言えば、 tmpの役割は、 forループのiのように、リストの走査のみです。
printList(list)の再帰的バリアントは単純なロジックに従います。リストを出力するには、現在の要素listを出力し、同じことをlist.nextに対して実行する必要があります。
let リスト = {
値: 1、
次： {
値: 2、
次： {
値: 3、
次： {
値: 4、
次へ: null
}
}
}
};
関数 printList(リスト) {
アラート(リスト.値); // 現在の項目を出力します
if (リスト.ネクスト) {
printList(list.next); // リストの残りの部分に対しても同じことを行います
}
}
printList(リスト);さて、何が良いでしょうか？
技術的には、ループの方が効果的です。これら 2 つのバリアントは同じことを行いますが、ループはネストされた関数呼び出しにリソースを消費しません。
逆に言えば、再帰的なバリアントは短く、理解しやすい場合もあります。
重要度: 5
前のタスクの単一リンク リストを出力します。 逆の順序で単一リンク リストを出力します。
ループを使用する方法と再帰を使用する方法の 2 つの解決策を作成します。
ここでの再帰ロジックは少し注意が必要です。
まずリストの残りの部分を出力し、次に現在のリストを出力する必要があります。
let リスト = {
値: 1、
次： {
値: 2、
次： {
値: 3、
次： {
値: 4、
次へ: null
}
}
}
};
関数 printReverseList(リスト) {
if (リスト.ネクスト) {
printReverseList(list.next);
}
アラート(リスト.値);
}
printReverseList(リスト);ループのバリアントも、直接出力よりも少し複雑です。
listの最後の値を取得する方法はありません。私たちも「戻る」ことはできません。
したがって、私たちができることは、まず項目を直接の順序で調べて配列で記憶し、次に記憶したものを逆の順序で出力することです。
let リスト = {
値: 1、
次： {
値: 2、
次： {
値: 3、
次： {
値: 4、
次へ: null
}
}
}
};
関数 printReverseList(リスト) {
arr = []; とします。
tmp = リストとします。
while (tmp) {
arr.push(tmp.value);
tmp = tmp.next;
}
for (let i = arr.length - 1; i >= 0; i--) {
アラート( arr[i] );
}
}
printReverseList(リスト);再帰的ソリューションは実際にはまったく同じことを行うことに注意してください。リストに従い、ネストされた呼び出しのチェーン (実行コンテキスト スタック内) 内の項目を記憶し、それらを出力します。