尝试了解JavaScript中的循环内的递归 [英] Trying to understand recursion within for loops in javascript
问题描述
感谢您的洞察力。
var permArr = []，
usedChars = [];
函数permute（input）{
var i，ch; （i = 0; i< input.length; i ++）{
ch = input.splice（i，1）[0];
。
usedChars.push（ch）;
if（input.length == 0）{
permArr.push（usedChars.slice（））;
}
permute（输入）;
input.splice（i，0，ch）;
usedChars.pop（）;
}
return permArr
};
$ b
从两个数组开始，这两个数组将具有全局作用域： permArray 将最终包含所有的置换数组，并且 usedChars 是一个工作数组，通过所有递归调用构建每个单独的置换数组。需要注意的是，这些都是 两个变量，可以在每个创建的函数的范围内访问。所有其他变量对本身的函数调用都具有局部作用域。
然后是递归函数，它接受一个数组作为输入，并返回一个数组的数组，其中包含所有可能的排列输入数组。现在，在这个特定的函数中，递归调用是在一个循环内。这很有趣，因为终止条件实际上比您的基本递归函数更复杂 - 递归调用在传入一个空的 input 数组并且for循环跳过下一个递归调用。
$ b
小结
考虑四元素数组输入。在高层次上，函数将循环遍历这个数组的四个元素，拉出每个元素，并计算三个元素的较小数组的排列。所有这三个元素的排列，它将追加到原来的元素，并将这四个元素数组中的每一个添加到 permArray 。
$但是，为了找到较小的两个元素数组的排列，我们抽出每个元素，计算一个元素的较小数组的排列，添加从每个元素的开始拉出的元素permutations和 return 这两个元素数组的每一个递归调用堆栈，所以原来的第三个元素可以添加到开始但是，为了找到较小的一个元素数组的排列，我们抽出元素并计算排列那个刚刚返回的空数组，然后我们又将我们的一个元素返回到堆栈，所以原来的第二个元素可以被添加到该排列的开始处，并返回到堆栈中。
$
$ b $ h
$
var permArr = []，
usedChars = [];
函数permute（input）{
var i，ch;
for（i = 0; i< input.length; i ++）{//遍历所有元素
ch = input.splice（i，1）[0]; // 1。依次拉出每个元素
usedChars.push（ch）; / /推这个元素
if（input.length == 0）{// 2。如果输入是空的，我们推送每个元素
permArr.push（usedChars.slice（））; //将它作为一个排列添加
}
permute（input）; // 3。计算小数组
input.splice（i，0，ch）的排列; // 4。将原始元素添加到开始
//使输入的大小与我们开始
//时的大小相同//但以不同的顺序
usedChars.pop（）; // 5。删除我们推送的元素
}
返回permArr //返回，但这只在最后一次调用
}时才有意义;
让我们使用数组[4,3,2,1]追踪细节。
当它第一次传入时，我们将取出4，将它推到 这给我们留下了四个深度调用，在步骤（2）中： 步骤（4）将执行算法的关键步骤：移动动作。它将 现在看看我们在哪里。我们把[4,3,2,1]作为一个置换，然后备份和交换2和1，现在我们将回到递归调用来构建[4,3， 1,2]并添加它作为一个排列。回过头来看，在步骤（5）之后，我们会看到更多的元素，然后返回到排列并添加它们。 被执行我们循环。这意味着我们将推送1到 我希望这有助于！ I've been staring at the answer to this question forever even writing down variables and whatnot through each iteration. I simply just don't get the process here. When I throw in console logs I see that permute is called input.length - 1 times before it ever gets to this line input.splice(i, 0, ch); It's hard to phrase the question when I am lost completely, but I guess some curiosities are: each time permute is called, it is a new instance of that function with it's own closure right? therefore variables changes that are within the function won't affect variables in other calls? does the function return permArr for each time it's called? and I suppose that doesn't necessarily affect the return of the first call? (my instinct tells me that the first time return happens, the function stops running). Thanks for the insight.
I'll give this a shot. You start with two arrays that will have global scope: Then there is the recursive function which accepts an array as input and returns an array of array with all possible permutations of the input array. Now, in this particular function the recursive call is inside a loop. This is interesting because the terminating condition is actually more complicated than your basic recursive function--the recursive calls terminate when you pass in an empty Consider a four element array input. At a high level, the function is going to loop over the four elements of this array, pull out each element, and compute the permutation of that smaller array of three elements. With all of those three element permutations, it will append the original element pulled out to the beginning and add each of those four element arrays to But, in order to find the permutation of the smaller three element arrays, we pull out each element, compute the permutation of that smaller array of two elements, add the element pulled out to the beginning of each of those permutations, and return each of those three element arrays up the recursion call stack so the original fourth element can be added to the beginning and counted as a permutation. But, in order to find the permutation of the smaller two element arrays, we pull out each element, compute the permutation of that smaller array of one element, add the element pulled out the the beginning of each of those permutations, and return each of those two element arrays up the recursion call stack so the original third element can be added to the beginning of that permutation and returned up the stack. But, in order to find the permutation of the smaller one element array, we pull out the element and compute the permutation of that empty array, which just returns, and we in turn just return our one element back up the stack so the original second element can be added to the beginning of that permutation and returned up the stack. Let's note some of the steps in this function: Let's trace through the details using the array [4,3,2,1]. When it's first passed in, we'll take out the 4, push it to This leaves us four calls deep and at step (2) with:
ch=1
input=[]
usedChars=[4,3,2,1] At step (2), we're going to push our first permutation [4,3,2,1] to So, at this point, we have started backing up our recursive calls and sit at step (4) with:
ch=2
input=[1]
usedChars=[4,3,2] Step (4) will perform the critical step of the algorithm: the moving action. It takes Now take a look at where we are. We pushed [4,3,2,1] as a permutation, then backed up and swapped 2 and 1, and now we're going to go back into recursive calls to build [4,3,1,2] and add it as a permutation. After that we will back out some more, move around some more elements, and go back into the permutations and add them. Getting back into it, after step (5) is executed we loop. That means we will push 1 to So, you're going to cycle up and down through the recursive calls building up a permutation, backing back out, rebuilding a different permutation, and backing out until you've looped over every possible combination. I hope this helps! 这篇关于尝试了解JavaScript中的循环内的递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！ usedChars ，将其从输入中移除，在[3,2,1]上调用 permute 。在这个调用中，我们将3推到 usedChars ，从 input 中移除，并调用 [2,1]上的> permute 。然后我们把2推到 usedChars ，从输入中移除它，并且调用 permute on [1 ]。然后我们推1到 usedChars ，并从 input`中移除它。
$ b
ch = 1
input = []
usedChars = [4,3,2,1]
在步骤（2）中，我们将把我们的第一个置换[4,3,2,1]推到 permArr 。然后，继续，因为 input 现在是空的，（3）中的递归调用将简单地返回，在（4）中，我们将简单地将1加回到输入中，并将1从 usedChars - 这个调用返回。因此，在这一点上，我们已经开始备份我们的递归调用，并在步骤（4）中使用：
ch = 2
input = [1]
usedChars = [4,3,2]
ch = 2 并将其添加到 input 的开头，并将其从 usedChars 。这意味着在步骤（5）之后，我们有：
ch = 2
input = [2,1]
usedChars = [4,3]
usedChars ，并使用 input = [2] 进行递归调用。这个调用会将2推到 usedChars 中，创建一个完整的数组[4,3,1,2]，并将它添加到 permArray 。所以，你要通过递归调用循环，建立一个排列，退后，重建一个不同的排列，然后退出，直到你已经结束了所有可能的组合。
var permArr = [],
usedChars = [];
function permute(input) {
var i, ch;
for (i = 0; i < input.length; i++) {
ch = input.splice(i, 1)[0];
usedChars.push(ch);
if (input.length == 0) {
permArr.push(usedChars.slice());
}
permute(input);
input.splice(i, 0, ch);
usedChars.pop();
}
return permArr
};
Overview
permArray will eventually hold all of the permutation arrays, and usedChars is a worker array used build each individual permutation array through all of the recursive calls. It's important to note that these are the only two variables that are accessible in the scope of every function created. All other variables have local scope to their own function call.input array and the for loop skips over the next recursive call.Summary
permArray.Details
var permArr = [],
usedChars = [];
function permute(input) {
var i, ch;
for (i = 0; i < input.length; i++) { // loop over all elements
ch = input.splice(i, 1)[0]; //1. pull out each element in turn
usedChars.push(ch); // push this element
if (input.length == 0) { //2. if input is empty, we pushed every element
permArr.push(usedChars.slice()); // so add it as a permutation
}
permute(input); //3. compute the permutation of the smaller array
input.splice(i, 0, ch); //4. add the original element to the beginning
// making input the same size as when we started
// but in a different order
usedChars.pop(); //5. remove the element we pushed
}
return permArr //return, but this only matters in the last call
};
usedChars, remove it from input, and call permute on [3,2,1]. In this call, we'll push 3 to usedChars, remove it from input, and call permute on [2,1]. Then we push 2 to usedChars, remove it from input, and callpermuteon [1]. Then we push 1 tousedChars, and remove it frominput`. permArr. Then, moving on, since input is now empty the recursive call in (3) will simply return and in (4) we will simply add 1 back into input and remove 1 from usedChars--and this call returns. ch=2 and adds it to the beginning of input and removes it from usedChars. This means that after step (5), we have:
ch=2
input=[2,1]
usedChars=[4,3]usedChars and make a recursive call with input=[2]. That call will push 2 into usedChars creating a the full array [4,3,1,2] and causing it to be added to permArray.
