JavaScript 再帰の再帰とループの例

繰り返しの計算が必要なさまざまなタイプの問題に対して、ループおよび再帰メソッドにはそれぞれ利点があり、より直感的で簡単な解決策を提供できます。興味のある方は次へ

をご覧ください。再帰とループ

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

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

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

//pseudo code of a loop 
//while形式 
function loop(arguments){ 
//结果的初始值 
result:=initial_value; 
while(condition(variable, arguments)){//循环条件，可能只需arguments，也可能为了方便引入循环变量 
//计算结果。参数包括之前的结果、当前循环变量和外部变量 
result:=calculate(result, variable, extern_variables); 
//影响函数的外部环境，即修改外部变量 
changeStatus(result, variable, extern_variables); 
//执行完循环体中的语句后，修改参数或循环变量。 
modify_arguments_variable(arguments, variable); 
} 
//返回结果 
return result; 
}

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

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

//pseudo code of a recursion 
function recursion(arguments){ 
//以下代码为控制函数重复调用的结构部分。 
//获得再次调用此函数的新的参数，可能为多组arguments值。 
//对应于循环中的condition(variable, arguments)和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, arguments, extern_variables); 
return result; 
}

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

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

//loop 
function sum(num){ 
var result=1; 
while (num>1){ 
result+=num; 
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 (a<b){ 
temp=a; 
a=b; 
b=temp; 
} 
var c=a%b; 
while (c!==0){ 
a=b; 
b=c; 
c=a%b; 
} 
return b; 
}

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

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为单个class名 
//返回包含elem下所有class属性包含给定名称的element的数组 
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; i<c.length; i++){ 
getElements(c[i]); 
} 
} 
getElements(elem); 
return list; 
}

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

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

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

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

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

ループバージョンの使用:


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

getElementsByClass.loop1 = function(elem, name){ 
//use a js array as the basis of a needed stack 
var stack = []; 
stack.get = function(){ 
return stack[stack.length - 1]; 
} 
var list = []; 
//the business logic part. put the eligible element to the list. 
function testElem(el){ 
if (el.className.split(' ').indexOf(name) > -1) { 
list.push(el); 
} 
} 
//check the root element 
testElem(elem); 
//initialize the stack 
stack.push({ 
pointer: elem, 
num: 0 
}); 
var parent, num, el; 
while (true) { 
parent = stack.get(); 
el = parent.pointer.children[parent.num]; 
if (el) {//enter a deeper layer of the tree 
testElem(el); 
stack.push({ 
pointer: el, 
num: 0 
}); 
} 
else {//return to the upper layer 
if (stack.pop().pointer === elem) { 
break; 
} 
else { 
stack.get().num += 1; 
} 
} 
} 

return list; 
}

归纳起来。所有循环都可以用递归实现；所有递归都可以用循环实现。采用哪种方法，由具体问题下哪种思路更方便直观和使用者的喜好决定。

效率

性能方面，递归不比循环有优势。除了多次函数调用的开销，在某些情况下，递归还会带来不必要的重复计算。以计算斐波那契数列的递归程序为例。求第n项A(n)时，从第n-2项起，每一项都被重复计算。项数越小，重复的次数越多。令B(i)为第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)

换一个角度来看，令C(i)为求A(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较大时，前面给出的采用循环的程序会比采用递归的程序快很多。

如上一节中的循环一样，递归中的这个缺陷也是可以弥补的。我们只需要记住已经计算出来的项，求较高项时，就可以直接读取以前的项。这种技术在递归中很普遍，被称为“存储”(memorization)。

下面是采用存储技术的求斐波那契数列的递归算法。

代码如下:

//recursion with memorization 
function fibonacci4(n){ 
var memory = []; //used to store each calculated item 
function calc(n){ 
var result, p, q; 
if (n < 2) { 
memory[n] = n; 
return n; 
} 
else { 
p = memory[n - 1] ? memory[n - 1] : calc(n - 1); 
q = memory[n - 2] ? memory[n - 2] : calc(n - 2); 
result = p + q; 
memory[n] = result; 
return result; 
} 
} 
return calc(n); 
}

更多JavaScript的递归之递归与循环示例介绍相关文章请关注PHP中文网！