javascript - 生成字符串排列的递归函数

Question

//====================================================
function getPermutations(str){
    //Enclosed data to be used by the internal recursive function permutate():
    var permutations = [],  //generated permutations stored here
        nextWord = [],      //next word builds up in here     
        chars = []          //collection for each recursion level
    ;
    //---------------------
    //split words or numbers into an array of characters
    if (typeof str === 'string') chars = str.split(''); 
    else if (typeof str === 'number') {
      str = str + ""; //convert number to string
      chars = str.split('');//convert string into char array
    }
    //============TWO Declaratives========
    permutate(chars);
    return permutations;
    //===========UNDER THE HOOD===========
    function permutate(chars){ //recursive: generates the permutations
        if(chars.length === 0)permutations.push(nextWord.join(''));            
        for (var i=0; i < chars.length; i++){
            chars.push(chars.shift());  //rotate the characters
            nextWord.push(chars[0]);    //use the first char in the array            
            permutate(chars.slice(1));  //Recurse: array-less-one-char
            nextWord.pop();             //clear for nextWord (multiple pops)
        }
    }
    //--------------------------------
}//==============END of getPermutations(str)=============

nextWord.pop() 如何被多次调用？不会排列(chars.slice(1));不要让 nextWord.pop() 执行，因为它会将您带回排列函数的顶部？

此外，当 chars 因调用 slice 而变空时 permutate(chars.slice(1));谁再次填充字符？字符是否由 nextWord.pop() 填充；因为 pop 将值返回给排列函数？

在 Chrome 调试器中单步执行此代码并不清楚。

Answer 1

递归调用permutate位于循环内，每次执行时都会将其放入调用堆栈中。 nextWord.pop 被多次调用以完成堆栈上每个递归调用的执行。您可以使用此工具可视化递归 http://visualgo.net/recursion.html 。如果您有 Webstorm 之类的工具，则可以在调试器中运行它，以在第一次调用 nextWord.pop 时看到堆栈中有 3 个 permutate() 调用。