Explication détaillée du code des avantages respectifs de la récursivité et des boucles de JavaScript

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 fournir des solutions plus intuitives et simples. 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.

//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.

//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 en effectuant 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 cumulative simple suivante :

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

La forme récursive correspondante :

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

Au contraire, la plupart des programmes récursifs peuvent aussi être directement bouclé à réaliser. Ce qui suit est une fonction sous forme de boucle qui trouve le plus grand diviseur commun.

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 facile. 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 une boucle si nous mémorisons certaines informations sur la position du nœud à l'aide d'une structure de données dans la boucle.

Pour résumer. Toutes les boucles peuvent être implémentées en utilisant la récursion ; toute la récursion peut être implémentée en utilisant des boucles. La méthode utilisée dépend de l'idée la plus pratique et la plus intuitive pour le problème spécifique et les préférences de l'utilisateur.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!