今天看看一些实战中用到递归的例子,第一个就是字符串全排列了,例如:

字符串'abc',那么全排列结果是:['abc','acb','bac','bca','cab','cba'],

字符串'abb',那么全排列结果是:['abb','bab','bba']。

这里我们可以假设f(str)代表str的全排列,那么f(abc)的全排列可以表示为[a+f(bc),b+f(ac),c+f(ab)],这样逐层展开,我们就可以求出一个字符串的全排列。

那么我们可以写出代码:

var f=function(str){
    return str.length==1?[str]:Array.from(new Set(str.split('').map((char,i)=>{
        return f(str.substr(0,i)+str.substr(i+1)).map((_char)=>{
        return char+_char;
        })
    }).reduce((rs,item)=>rs.concat(item),[])));
}

上面代码还是比较难懂,其中Array.from(new Set())这种是数组去重的,因为全排列的时候会有一些重复的情况。上面的代码中有两层map和一个reduce,这个还是有点难理解的,我们看一个具体的过程:

斐波那契数列就是指f(n)=f(n-1)+f(n-2)的数列,其中f(0)=0,f(1)=1。计算f(n)的数值很容易让人产生一种错觉,让人很自然的觉得用递归的方法去做,例如如下结构:

其实这种是一种不正确的思路,因为这里面有大量重复的计算,而且是指数级别的,正确的做法就是从头开始遍历而不是从尾部开始递归。

function f(n){
    if(n==0){
        return 0;
}else if(n==1){
    return 1;
    }else {
        let first=0,second=1,third;
    for(let i=2;i<=n;i++){
            third=first+second;
            first=second;
            second=third;
}
        return third;
    }
}

青蛙跳台问题说的是有一个青蛙跳台阶,每次可以跳一格,也可以跳两格,问f(n)有多少种跳法。

首先f(1)=1,f(2)=2,现在假设要跳n台阶(n>2),那么青蛙可以选择先跳1格,剩下f(n-1)种跳法,或者先条2格,剩下f(n-2)种跳法,那么f(n)=f(n-1)+f(n-2)种跳法。这种其实就是上面的斐波那契数列了,解法相同,只不过初始值不同了。

回到顶部
我要评论

所有评论

返回
邮箱:
绑定
取消
×

我要评论

回复:

昵称:(昵称不超过20个字)

图片:

邮箱:
绑定邮箱后,若有回复,会邮件通知。
提交
还可以输入500个字