试图理解javascript中for循环中的递归

Question

我一直在盯着这个问题的答案,甚至在每次迭代中写下变量和诸如此类的东西.我只是不在这里得到这个过程.当我输入控制台日志时,我看到permute被称为input.length - 在它到达此行之前的1倍input.splice(i,0,ch); 当我完全迷失时很难说出这个问题,但我想有些好奇心是:每次调用permute时,它都是该函数的一个新实例,它有自己的闭包权吗？因此,函数内的变量变化不会影响其他调用中的变量？该函数每次被调用时都会返回permArr吗？而且我想这不一定会影响第一次通话的回归？(我的直觉告诉我第一次返回,函数停止运行).

感谢您的见解.

JavaScript中的排列？

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

Answer 1

我会试一试.

概观

您从两个具有全局范围的数组开始:permArray最终将保留所有排列数组,并且usedChars是一个工作数组,用于通过所有递归调用构建每个单独的排列数组.重要的是要注意,这些是在创建的每个函数的范围内可访问的唯一两个变量.所有其他变量都有自己的函数调用的局部范围.

然后是递归函数,它接受一个数组作为输入,并返回一个数组数组,其中包含输入数组的所有可能的排列.现在,在这个特定的函数中,递归调用是在循环内部.这很有趣,因为终止条件实际上比基本的递归函数更复杂 - 当你传入一个空input数组并且for循环跳过下一个递归调用时递归调用终止.

摘要

考虑一个四元素数组输入.在高级别,函数将循环遍历此数组的四个元素,拉出每个元素,并计算三个元素的较小数组的排列.对于所有这三个元素排列,它会将原始元素追加到开头并将这四个元素数组中的每一个添加到permArray.

但是,为了找到较小的三元素数组的排列,我们拉出每个元素,计算两个元素的较小数组的排列,将元素拉出到每个排列的开头,并返回每个元素这三个元素在递归调用堆栈中排列,因此原始的第四个元素可以添加到开头并计为置换.

但是,为了找到较小的两个元素数组的排列,我们拉出每个元素,计算一个元素的较小数组的排列,添加从每个排列的开头拉出的元素,并返回每个元素递归调用堆栈中的那两个元素数组,因此原始的第三个元素可以添加到该排列的开头并返回堆栈.

但是,为了找到较小的一个元素数组的排列,我们拉出元素并计算刚刚返回的那个空数组的排列,然后我们又将我们的一个元素返回到栈中,这样原来的第二个元素可以添加到该排列的开头并返回堆栈.

细节

我们来看一下这个函数的一些步骤:

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

让我们使用数组[4,3,2,1]来追踪细节.

当它第一次传入时,我们将取出4,将其推入usedChars,从输入中删除它,然后调用permute[3,2,1].在这次通话中,我们将推送3 usedChars,将其从中删除input,然后调用permute[2,1].然后,我们推2 usedChars,从删除它input, and call置换on [1]. Then we push 1 tousedChars , and remove it frominput`.

这留下了四个深度调用,在步骤(2)中: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]

步骤(4)将执行算法的关键步骤:移动动作.这需要ch=2并将其添加到开始的input和删除它usedChars.这意味着在步骤(5)之后,我们得到:
ch = 2 input = [2,1] usedChars = [4,3]

现在来看看我们在哪里.我们推[4,3,2,1]作为排列,然后备份并交换 2和1,现在我们将回到建立[4,3,1,2]的递归调用并添加它作为一种排列.在那之后,我们将退出更多,移动一些更多的元素,然后回到排列并添加它们.

回到步骤(5)之后,我们循环.这意味着我们将推送1 usedChars并进行递归调用input=[2].该调用将推动2 usedChars创建一个完整的数组[4,3,1,2]并导致它被添加到permArray.

因此,您将在递归调用中上下循环,建立排列,退回,重建不同的排列,并退出,直到您循环遍历每个可能的组合.

我希望这有帮助!