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

    字符串'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)],这样逐层展开,我们就可以求出一个字符串的全排列。

    那么我们可以写出代码:

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

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

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

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

    1. function f(n){
    2.     if(n==0){
    3.         return 0;
    4. }else if(n==1){
    5.     return 1;
    6.     }else {
    7.         let first=0,second=1,third;
    8.     for(let i=2;i<=n;i++){
    9.             third=first+second;
    10.             first=second;
    11.             second=third;
    12. }
    13.         return third;
    14.     }
    15. }

    青蛙跳台问题说的是有一个青蛙跳台阶,每次可以跳一格,也可以跳两格,问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)种跳法。这种其实就是上面的斐波那契数列了,解法相同,只不过初始值不同了。

    回到顶部
    我要评论

    所有评论

      相关文章