Detailed code explanation of the respective advantages of recursion and loops in JavaScript

Recursion and Loop

For different types of problems that require repeated calculations, loop and recursion methods have their own advantages and can provide more intuitive and simple solutions. On the other hand, loop and recursive methods can be converted into each other. Any loop of code can be rewritten using recursion to achieve the same function; and vice versa. Without losing their generality, loops and recursions can be summarized using the following pseudocode respectively.

Pseudocode format description: The loop adopts the while form; variables are not defined; assignment uses:=; conditional expressions and executed statements are written in the form of functions, and relevant values ​​are written in parentheses. In terms of other syntax, try to be as close to the Javascript specifications as possible.

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

Similarly we give the pseudo code of the recursive function.

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

Comparing the two pieces of code, we can see that loops and recursions have similar compositions. By changing the order and making appropriate transformations, any loop can be implemented in a recursive way. This transformation is easy to see when the program is simple. For example, the following simple cumulative sum function:

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

The corresponding recursive form:

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

On the contrary, most recursive programs can also be implemented directly by loops. The following is a function in the form of a loop that finds the greatest common divisor.

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

However, the conversion from recursion to loop is not always so easy. The part of the recursive pseudocode that generates new arguments for calling this function again

new_arguments:=conditional_get_next(arguments);

is more flexible than the corresponding part of the loop. Recursion can be divided into two categories according to the number of newly generated parameter groups (all parameters required by the function are one group). The first type is when the number of parameter groups is fixed, and the recursion can be converted into a loop, such as the Fibonacci sequence and the greatest common divisor example; the second type is when the number of parameter groups is uncertain - just like when traversing a graph or tree That way, each point has any number of adjacent points - this recursion cannot be directly converted into a loop.

Because loops can only do one-dimensional repetitions, while recursion can traverse two-dimensional structures. For example, in a tree, a node has both its child nodes and nodes at the same level. A simple one-dimensional loop cannot traverse in both directions. But the second type of recursion can also be implemented with a loop if we remember some information about the node position with the help of some data structure in the loop.

To summarize. All loops can be implemented using recursion; all recursion can be implemented using loops. Which method is used depends on which idea is more convenient and intuitive for the specific problem and the user's preferences.

The above is the detailed content of Detailed code explanation of the respective advantages of recursion and loops in JavaScript. For more information, please follow other related articles on the PHP Chinese website!