Introduction à la récursivité et exemples de boucles de récursivité JavaScript

Pour différents types de problèmes nécessitant des calculs répétés, les méthodes de boucle et de récursion ont leurs propres avantages et peuvent fournir une solution plus intuitive et simple. Ce qui suit est une introduction détaillée à la récursivité et à la boucle de JavaScript pour ceux qui sont intéressés. découvrez la

Récursion et boucle

Pour différents types de problèmes nécessitant des calculs répétés, les méthodes de boucle et de récursion ont leurs propres avantages et peuvent donner une solution simple plus intuitive. D'un autre côté, les méthodes de boucle et récursives peuvent être converties les unes dans les autres. N'importe quelle boucle de code peut être réécrite en utilisant la récursion pour obtenir la même fonction et vice versa ; Sans perdre leur généralité, les boucles et récursions peuvent être résumées à l’aide du pseudocode suivant.

Description du format de pseudocode : la boucle adopte la forme while ; les variables ne sont pas définies ; les expressions conditionnelles et les instructions exécutées sont écrites sous forme de fonctions, et les valeurs pertinentes sont écrites entre parenthèses. En termes d’autres syntaxes, essayez d’être aussi proche que possible des spécifications Javascript.

Le code est le suivant :

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

De même nous donnons le pseudo code de la fonction récursive.

Le code est le suivant :

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

En comparant les deux morceaux de code, nous pouvons voir que les boucles et les récursions ont des compositions similaires. En changeant l'ordre et les transformations appropriées, n'importe quelle boucle peut être implémentée de manière récursive. Cette transformation est facile à constater lorsque le programme est simple. Par exemple, la fonction somme cumulée simple suivante :

Le code est le suivant :

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

La forme récursive correspondante :
Le code est le suivant :

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

Au contraire, la plupart des programmes récursifs peuvent également être implémentés directement par des boucles. Ce qui suit est une fonction sous forme de boucle qui trouve le plus grand diviseur commun.

Le code est le suivant :

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

Cependant, la conversion de la récursivité en boucle n'est pas toujours aussi simple. La partie du pseudocode récursif qui génère de nouveaux arguments pour appeler à nouveau cette fonction

new_arguments:=conditional_get_next(arguments);

est plus flexible que la partie correspondante de la boucle. La récursivité peut être divisée en deux catégories en fonction du nombre de groupes de paramètres nouvellement générés (tous les paramètres requis par la fonction constituent un groupe). Le premier type est lorsque le nombre de groupes de paramètres est fixe et la récursion peut être convertie en boucle, comme la séquence de Fibonacci et l'exemple du plus grand diviseur commun ; le deuxième type est lorsque le nombre de groupes de paramètres est incertain - tout comme lors du parcours d'un graphique ou d'un arbre De cette façon, chaque point a un nombre quelconque de points adjacents - cette récursivité ne peut pas être directement convertie en boucle.

Parce que les boucles ne peuvent effectuer que des répétitions unidimensionnelles, tandis que la récursivité peut traverser des structures bidimensionnelles. Par exemple, dans un arbre, un nœud a à la fois ses nœuds enfants et ses nœuds au même niveau. Une simple boucle unidimensionnelle ne peut pas parcourir dans les deux sens.

Mais le deuxième type de récursivité peut également être implémenté avec des boucles si l'on se souvient de certaines informations sur la position du nœud à l'aide d'une structure de données.

Utilisons un autre exemple pour mettre en pratique la conclusion tirée de l’observation ci-dessus. HTML5 définit une nouvelle méthode getElementsByClassName(names) pour Document et Element, qui renvoie tous les éléments avec une valeur de classe donnée. Certains navigateurs, dont Firefox 3, prennent déjà en charge cette méthode. Ci-dessous, nous utilisons d'abord une méthode récursive pour donner une version plus faible, puis nous la réécrivons en utilisant une méthode de boucle.

Le code est le suivant :

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

Comme mentionné ci-dessus, afin de mémoriser les informations de position du nœud dans la boucle, nous avons besoin d'une structure de données qui puisse implémenter la méthode suivante.

push(object) //Écrire un objet.

objectpop() //Lire l'objet le plus récemment écrit et le supprimer de la structure de données.

objectget() //Lire l'objet le plus récemment écrit sans modifier le contenu de la structure de données.

La pile est exactement une telle structure de données dernier entré, premier sorti. L'objet Array en Javascript prend en charge les deux premières méthodes, et nous pouvons y ajouter une troisième méthode.

La version en boucle :

Le code est le suivant :

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