JavaScript の再帰とループの例の紹介 recursion_javascript スキル

再帰とループ

繰り返しの計算が必要なさまざまなタイプの問題に対して、ループおよび再帰手法にはそれぞれ利点があり、より直感的でシンプルな解決策を提供できます。一方、ループメソッドと再帰メソッドは相互に変換できます。コードのループは再帰を使用して書き換えることができ、その逆も可能です。一般性を失うことなく、ループと再帰は次の疑似コードを使用して要約できます。

疑似コードの形式の説明: ループは while 形式を採用し、変数は定義されません。代入の条件式と実行されるステートメントは関数の形式で記述され、関連する値は括弧内に記述されます。他の構文に関しては、JavaScript の仕様にできるだけ近づけるようにしてください。

コードをコピー コードは次のとおりです:

//ループの疑似コード
// while form
functionloop(arguments){
//結果の初期値
result:=initial_value;

while(condition(variable, argument)){/ /ループ条件、可能 引数のみが必要で、便宜上ループ変数を導入することもできます
//計算結果。パラメータには、前の結果、現在のループ変数、外部変数が含まれます。
result:=calculate(result, variable, extern_variables);
//関数の外部環境に影響を与えます。つまり、外部変数を変更します。
changeStatus( result, variable , extern_variables);
//ループ本体内のステートメントを実行した後、パラメーターまたはループ変数を変更します。
modify_arguments_variable(arguments, variable);
}
//Return result
return result;
}

同様に再帰関数の疑似コードを与えます。 。

コードをコピー コードは次のとおりです:

//再帰の疑似コード
function recursion (arguments){
//次のコードは、関数の繰り返し呼び出しを制御する構造部分です。
//この関数を再度呼び出すための新しいパラメータを取得します。これは複数の引数値のセットである場合があります。
//ループ内のcondition(variable, argument) およびmodify_arguments_variable(arguments, variable)に対応します。
new_arguments:=conditional_get_next(arguments);
//新しいパラメーターのグループごとに、関数自体を呼び出します。
results:=recursion(new_arguments);

//次のコードは、呼び出されるたびに実行される機能部分です。
//結果を計算します。以前の結果、現在のループ変数、および外部変数が含まれます。
//ループ内の result:=calculate(result, variable, extern_variables) に対応します。
result:=calculate(arguments, extern_variables);
result:=combine(result, results);
//関数の外部環境に影響を与える、つまり、外部変数を変更します
changeStatus (result, argument, extern_variables);
return result;
}

2 つのコードを比較すると、順序と再帰が似たような構成になっていることがわかります。適切な変換を行うと、任意のループを再帰的に実装できます。プログラムが単純な場合、この変化は簡単に確認できます。たとえば、次の単純な累積和関数:

コードをコピー コードは次のとおりです:

// ループ
関数 sum(num){
var result=1;
result =num;
; 🎜>return result;
}


対応する再帰形式:

コードをコピー コードは次のとおりです。 //recursion

function sum2(num){

if (num>1){
return num sum(num-1); 🎜>}else {
return 1;
}
}


逆に、ほとんどの再帰プログラムはループによって直接実装することもできます。以下は、最大公約数を見つけるループ形式の関数です。

コードをコピー

コードは次のとおりです。 function gcd2(a, b){ var temp;

if (aa=b;
b=temp;
while (c!==0){
a=b;
c=a%b;
return
}


ただし、再帰からループへの移行は必ずしも簡単ではありません。この関数を再度呼び出すための新しい引数を生成する再帰擬似コードの部分

new_arguments:=conditional_get_next(arguments);

は、ループの対応する部分よりも柔軟です。再帰は、新しく生成されるパラメータ グループの数に応じて 2 つのカテゴリに分類できます (関数に必要なパラメータはすべて 1 つのグループです)。 1 つ目のタイプは、パラメータ グループの数が固定されており、フィボナッチ数列や最大公約数の例など、再帰をループに変換できる場合です。2 つ目のタイプは、パラメータ グループの数が不確実な場合です。グラフまたはツリーをトラバースするとき このように、各点には任意の数の隣接する点があります。この再帰を直接ループに変換することはできません。

ループは 1 次元の繰り返ししか実行できないのに対し、再帰は 2 次元の構造を横断できるためです。たとえば、ツリーでは、ノードにはその子ノードと同じレベルのノードの両方があります。単純な 1 次元ループは両方向に移動できません。

しかし、何らかのデータ構造を利用してノードの位置に関する情報を覚えていれば、2 番目のタイプの再帰もループで実装できます。

別の例を使用して、上記の観察から得られた結論を実践してみましょう。 HTML5 では、Document および Element に対して、指定されたクラス値を持つすべての要素を返す新しいメソッド getElementsByClassName(names) が定義されています。 Firefox 3 を含む一部のブラウザは、すでにこの方法をサポートしています。以下では、最初に再帰的メソッドを使用して弱いバージョンを提供し、次にループメソッドを使用してそれを書き直します。

コードをコピーします コードは次のとおりです。

var getElementsByClass={};
//elem は HTMLElement
//name は単一のクラス名です
//指定された名前を含む elem の下にあるすべてのクラス属性を持つ要素を含む配列を返します
getElementsByClass.recursion1=function (elem , name){
var list=[];
function getElements(el){
if (el.className.split(' ').indexOf(name)>-1){
list.push( el);
}
for (var i=0, c=el.children; igetElements(c[i]); }
}
getElements(elem);
return list;
}


前述のように、ループ内のノードの位置情報を記憶するには、次のメソッドのデータ構造を実装できる関数が必要です。

push(object) //オブジェクトを書き込みます。

objectpop() //最後に書き込まれたオブジェクトを読み取り、データ構造から削除します。

objectget() //データ構造の内容を変更せずに、最後に書き込まれたオブジェクトを読み取ります。

スタックはまさに​​後入れ先出しのデータ構造です。 Javascript の Array オブジェクトは最初の 2 つのメソッドをサポートしており、それに 3 番目のメソッドを追加できます。

ループバージョン:

コードをコピーします コードは次のとおりです:

getElementsByClass .loop1 = function(elem, name){

//必要なスタックの基礎として js 配列を使用します
var stack = []
stack.get = function(){
return stack[stack.length - 1];
}

var list = []
//対象となる要素をリストに追加します。 testElem(el ){
if (el.className.split(' ').indexOf(name) > -1) {
list.push(el)>}
}
// ルート要素を確認します
testElem(elem);
// スタックを初期化します
stack.push({
pointer: elem,
num: 0
});
varparent, num, el;
while (true) {
parent = stack.get();
el =parent.pointer.children[parent.num]; el) { // ツリーのより深い層に入ります
testElem(el)
stack.push({
pointer: el,
num: 0
}); }
else {//上の層に戻ります
if (stack.pop().pointer === elem) {
break;
}
else {
スタック。 get() .num = 1;
}
}
}

リストを返します。
要約すると。すべてのループは再帰を使用して実装できます。すべての再帰はループを使用して実装できます。どの方法が使用されるかは、特定の問題やユーザーの好みに対して、どちらのアイデアがより便利で直観的であるかによって決まります。

効率

パフォーマンスの点では、再帰はループよりも利点がありません。複数の関数呼び出しのオーバーヘッドに加えて、場合によっては再帰により不必要な計算が繰り返される可能性があります。たとえば、フィボナッチ数列を計算する再帰プログラムを考えてみましょう。 n 番目の項目 A(n) を求める場合は、n-2 番目の項目から順に各項目を繰り返し計算します。項目数が少ないほど繰り返し回数が多くなります。 i 番目の項目が計算される回数を B(i) とすると、

B(i)=1、i=n, n-1

B となります。 (i)=B(i 1) B(i 2); i
このようにして、B(i) は興味深い逆フィボナッチ数列を形成します。 A(n)を求める場合:

B(i)=A(n 1-i)

見方を変えると、A(i)を求めるときはC(i)とします。必要な加算数は次のとおりです:

C(i)=0; i=0, 1

C(i)=1 C(i-1) C(i-1) ; i>1

D(i)=C(i) 1 とすると、

D(i)=1; i=0, 1

D(i) )=D(i-1) D(i-1)

したがって、D(i) は別のフィボナッチ数列を形成します。そして、次のように結論付けることができます:

C(n)=A(n 1)-1

そして、A(n) は、n が小さくなると、等比級数で増加します。大きくなるとかなりびっくりします。ループを使用する対応するプログラムは

B(n)=1; n は任意の値です

C(n)=0; n=0, 1

C(n )=n-1; n>1

したがって、n が大きい場合、上記のループを使用したプログラムは再帰を使用したプログラムよりもはるかに高速になります。

前のセクションのループと同様、再帰におけるこの欠陥も補うことができます。計算された項を覚えておくだけでよく、より上位の項を見つけるときは、前の項を直接読み取ることができます。この手法は再帰で一般的であり、記憶と呼ばれます。

以下は、ストレージ テクノロジーを使用してフィボナッチ数列を見つけるための再帰的アルゴリズムです。

コードをコピー コードは次のとおりです:

//記憶付き再帰
関数fibonacci4(n ){
varmemory = []; //各計算項目の保存に使用
function calc(n){
var result, p,
if (n メモリ [n] = n;
return n;
else {
p = メモリ [n - 1] : calc(n - 1);
q = メモリ[n - 2] : 計算(n - 2);
メモリ[n] = 結果;結果;
}
}
戻り値
}