JavaScript で再帰アルゴリズムを実装する方法の紹介-jsチュートリアル-php.cn

JavaScript で再帰アルゴリズムを実装する方法の紹介

不言

リリース： 2019-03-23 11:42:54

転載

4170 人が閲覧しました

この記事では、JavaScript で再帰アルゴリズムを実装する方法を紹介します。一定の参考価値があります。必要な友人は参照してください。お役に立てば幸いです。

まず定義を見てみましょう。再帰的アルゴリズムは、問題をサイズが縮小された同じタイプのサブ問題に変換し、各サブ問題は同じアルゴリズムを使用して解決されます。一般に、再帰的アルゴリズムは、部分問題を解決するために自分自身を呼び出す関数です。

再帰アルゴリズムの特徴:

関数の処理中にそれ自体を呼び出します。
再帰処理では、再帰の終了、つまり再帰終了を判断するための明確な条件が必要です。
再帰アルゴリズムはシンプルですが非効率であるため、通常は推奨アルゴリズムとして推奨されません。

上記は百度百科の説明で非常に分かりやすいので、例を挙げてよく考えてください。

#Factorial

問題の説明: n! = n*(n-1)*...2*1

コードの実装:

JavaScript で再帰アルゴリズムを実装する方法の紹介

問題を取得したら、まず定義に従って同様のサブ問題にスケールを縮小します。たとえば、n! は n* (n-1)! に等しいため、(n-1)! = (n-1)*(n-2)! となります。この順番でif終了まで押し込みます。ここでは、arguments.callee は関数名の密結合を防ぐために使用されており、factorial(n-1) と同等です。関数の実装はシンプルかつ明確ですか?もちろん、問題の規模が単純なので実際にループを使って実装することも可能ですので、ぜひ試してみてください。

フィボナッチ数列

問題の説明: 1, 1, 2, 3, 5, 8, 13, 21, 34, ... .... n 番目の数値を求めます。

コードの実装:

下载 (1).png

実際、今のアイデアを実装するのは非常に簡単です。分析を通じて、最初の 2 つの数値の合計である n 番目の数値を取得できます。これにより、条件 n

The 問題

問題の説明: 階段には n 段あります。1 段ずつ上がることができます。または 1 つのステップで 2 つのステップ、またはレベル 3、異なる動きがいくつあるか数えます。

コードの実装:

下载 (2).png

これは実際にはフィボナッチ数列の実装です。分析すると、それを小規模なサブクラス問題に変換できます。指定されたはしごの最後の段に到達すると、3 つの状況が考えられます。1 つは 1 段上がった状態、2 は 2 段上がった状態、3 は 3 段上がった状態です。したがって、全体的な方法は F(n) = F(n-1) F(n-2) F(n-3) となります。そして、当然それは彼ら自身の小さな計算となり、判定条件が発生するまでそのサイクルが続きます。

最大公約数

問題の説明: 2 つの数値が与えられた場合、2 つの数値が等しい場合、最大公約数はそれ自体になります。それらが等しくない場合は、2 つの数値の減算の絶対値を取得し、2 つの数値の最小値と比較します。これらが等しい場合は、それが最大公約数です。等しくない場合は、上記のアルゴリズムを続行します。それらが等しくなるまで。コードの実装:

下载 (3).png 特に言うことはありません。問題の説明の要求に従って実装するだけです。再帰の出口は、a が b に等しいということです。

ハノイの塔

問題の説明: 誰もが多かれ少なかれプレイしたことがあるので、ここでは詳しく説明しません。コードの実装:

下载 (4).png 再帰の本質を理解するまで、私はこの問題にただ困惑していました。次にどこに行くべきかをどうやって知ることができるのか、私は常に自問しています。後になって、実は最後の部分をどうするかということのほうが気になっていたことに気づきました。どのようにこれを言うのですか？ディスクが 1 つしかない場合は、C 列または B 列に行かせることができると最初から考えることができます。もちろん、2 つのディスクでも実現できます。ディスク3枚でも大丈夫です。次に、4 つのディスクの状況について説明します。 4 つのディスクを完成させるには、A のディスクを完全に C に転送する必要があります。最初の 3 つのディスク全体を B に配置し、次に 4 番目のディスクを C に移動します。その後、最初の 3 つのディスクを C に配置すると、成功しました。最初の 3 つのゲームは新しいゲームとして扱うことができ、最初の 2 つのゲームは全体として扱うことができます。このように、全体的な大きなことだけに気を配ればよく、その他のことは小さな問題として解決できます。