javascript - 谁能给我讲讲关于递归的东西。。好难理解啊。。

问题描述

问 题

/**
 * Created by LR on 2016/12/7.
 */
function permutate(str) {
    var result = [];
    if(str.length == 1){
        return [str]
    }else {
        var preResult = permutate(str.slice(1))
        for (var j = 0; j < preResult.length; j++) {
            console.log(preResult[j])
            for (var k = 0; k < preResult[j].length+1; k++) {

                var temp=preResult[j].slice(0,k)+str[0]+preResult[j].slice(k);
                result.push(temp);
            }
        }
        console.log("!")
        console.log(result)
        return result
    }

}

permutate('abc');

第一次是abc 进入函数，然后长度大于1进入else；
所以这里就应该是
var preResult = permutate("bc")
之后呢？？我就想到bc进入函数，长度大于一
之后就 var preResult = permutate("c")
长度等于1了 然后就返回一个c 这个for循环是怎么执行的？？ 谁能告诉我一下。。。
这个是全排列的算法

解决方案

建议楼主先从最简单的两位字符递归开始分析，比如 permutate('ab');
它发生了什么呢，如下:

1.进入permutate函数内部，此时result为[]，由于'ab'的长度不是1，所以走到了else分支
2.取得的值 preResult = 'b'(这里递归了一次，取了后面的一位字符)
3.进入for循环，此时只将‘b’进行循环
4.进入关键的k(for)循环，循环了2次(注意，前面是一个字符串进入循环，所以k循环的次数是str.length+1)
5.k循环中

• k为0,生成一个tmp值'ab'('b'.slice(0,0)为空,str[0]为'a',‘b’.slice(0)为b)
  并且将那个'ab'push进result中

• k为1,生成一个tmp值‘ba’('b'.slice(0,1)为'b',str[0]为'a',‘b’.slice(1)为空)
  并且将那个'ba'push进result中

1. return result,所以这时最终的结果为['ab','ba']

同理,当三位字符递归时， permutate('abc');

1.进入permutate函数内部，此时result为[]，由于'abc'的长度不是1，所以走到了else分支
2.取得的值 preResult = ['bc','cb'] (就是上面一步中两位字符递归后的结果,只不过是将ab换为了bc)
3,进入for循环，此时for循环2次(分别为'bc'和'cb')

• ‘bc’循环时，进入关键的k循环，k循环的次数为3

  • k=0,tmp值为‘abc’

  • k=1,tmp值为'bac'

  • k=2,tmp值为'bca'

  • 循环结束后,result为['abc','bac','bca']

• ‘cb’循环时，进入关键的k循环，k循环的次数同样为3

  • k=0,tmp值为‘acb’

  • k=1,tmp值为'cab'

  • k=2,tmp值为'cba'

  • 循环结束后,result为['abc','bac','bca','acb','cab','cba']

4.返回最终的result，运行程序，发现结果完全匹配。分析结束。

接下来如果四位字符递归同理，路得一步一步走，莫急！

PS; ~码字不容易啊~

这篇关于javascript - 谁能给我讲讲关于递归的东西。。好难理解啊。。的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！