Rekursions- und Schleifenbeispiele der JavaScript-Rekursion

Für verschiedene Arten von Problemen, die wiederholte Berechnungen erfordern, haben Schleifen- und Rekursionsmethoden ihre eigenen Vorteile und können eine intuitivere und einfachere Lösung bieten. Im Folgenden finden Sie eine detaillierte Einführung in die JavaScript-Rekursion und -Schleife Erfahren Sie mehr über

Rekursion und Schleife

Für verschiedene Arten von Problemen, die wiederholte Berechnungen erfordern, haben Schleifen- und Rekursionsmethoden ihre eigenen Vorteile und können eine intuitivere, einfache Lösung bieten. Andererseits können Schleifen- und rekursive Methoden ineinander umgewandelt werden. Jede Codeschleife kann mithilfe der Rekursion umgeschrieben werden, um dieselbe Funktion zu erreichen, und umgekehrt. Ohne ihre Allgemeingültigkeit zu verlieren, können Schleifen und Rekursionen mit dem folgenden Pseudocode zusammengefasst werden.

Beschreibung des Pseudocode-Formats: Die Schleife verwendet die while-Form; bedingte Ausdrücke werden in Form von Funktionen geschrieben, und relevante Werte werden in Klammern geschrieben. Versuchen Sie in Bezug auf die sonstige Syntax, den Javascript-Spezifikationen so nahe wie möglich zu kommen.

Der Code lautet wie folgt:

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

Ähnlich geben wir den Pseudocode der rekursiven Funktion an.

Der Code lautet wie folgt:

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

Wenn wir die beiden Codeteile vergleichen, können wir sehen, dass Schleifen und Rekursionen ähnliche Zusammensetzungen haben, indem wir die Reihenfolge und entsprechende Transformationen ändern. Jede Schleife kann rekursiv implementiert werden. Diese Transformation ist leicht zu erkennen, wenn das Programm einfach ist. Zum Beispiel die folgende einfache kumulative Summenfunktion:

Der Code lautet wie folgt:

//loop 
function sum(num){ 
var result=1; 
while (num>1){ 
result+=num; 
num--; 
} 
return result; 
}

Die entsprechende rekursive Form:
Der Code lautet wie folgt :

//recursion 
function sum2(num){ 
if (num>1){ 
return num+sum(num-1); 
}else{ 
return 1; 
} 
}

Im Gegenteil, die meisten rekursiven Programme können auch direkt durch Schleifen implementiert werden. Das Folgende ist eine Funktion in Schleifenform, die den größten gemeinsamen Teiler ermittelt.

Der Code lautet wie folgt:

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

Allerdings ist die Konvertierung von Rekursion in Schleife nicht immer so einfach. Der Teil im rekursiven Pseudocode, der neue Argumente für den erneuten Aufruf dieser Funktion generiert

new_arguments:=conditional_get_next(arguments);

ist flexibler als der entsprechende Teil der Schleife. Die Rekursion kann entsprechend der Anzahl der neu generierten Parametergruppen in zwei Kategorien unterteilt werden (alle für die Funktion erforderlichen Parameter sind eine Gruppe). Der erste Typ ist, wenn die Anzahl der Parametergruppen fest ist und die Rekursion in eine Schleife umgewandelt werden kann, wie zum Beispiel die Fibonacci-Folge, und der zweite Typ ist, wenn die Anzahl der Parametergruppen unsicher ist – genau wie beim Durchlaufen eines Diagramms oder Baums Auf diese Weise hat jeder Punkt eine beliebige Anzahl benachbarter Punkte – diese Rekursion kann nicht direkt in eine Schleife umgewandelt werden.

Weil Schleifen nur eindimensionale Wiederholungen durchführen können, während eine Rekursion zweidimensionale Strukturen durchlaufen kann. In einem Baum befinden sich beispielsweise sowohl die untergeordneten Knoten als auch die Knoten eines Knotens auf derselben Ebene. Eine einfache eindimensionale Schleife kann nicht in beide Richtungen durchlaufen.

Aber die zweite Art der Rekursion kann auch mit Schleifen implementiert werden, wenn wir uns mithilfe einer Datenstruktur einige Informationen über die Knotenposition merken.

Lassen Sie uns die Schlussfolgerung aus der obigen Beobachtung anhand eines anderen Beispiels üben. HTML5 definiert eine neue Methode getElementsByClassName(names) für Document und Element, die alle Elemente mit einem bestimmten Klassenwert zurückgibt. Einige Browser, darunter auch Firefox 3, unterstützen diese Methode bereits. Im Folgenden verwenden wir zunächst eine rekursive Methode, um eine schwächere Version zu erhalten, und schreiben sie dann mithilfe einer Schleifenmethode neu.

Der Code lautet wie folgt:

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

Wie oben erwähnt, benötigen wir eine Datenstruktur, die implementiert werden kann, um sich die Positionsinformationen des Knotens in der Schleife zu merken die folgende Methode.

push(object) //Ein Objekt schreiben.

objectpop() //Das zuletzt geschriebene Objekt lesen und aus der Datenstruktur löschen.

objectget() //Das zuletzt geschriebene Objekt lesen, ohne den Inhalt der Datenstruktur zu ändern.

Der Stapel ist genau eine solche Last-In-First-Out-Datenstruktur. Das Array-Objekt in Javascript unterstützt die ersten beiden Methoden und wir können ihm eine dritte Methode hinzufügen.

Die Schleifenversion:

Der Code lautet wie folgt:

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中文网！