函数递归优化，js中应该如何写递归？

更新日期: 2022-04-15阅读: 1.2k标签: 递归分享

复制链接

新浪微博

QQ 好友

扫一扫分享

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2),  N > 2.

以最基础的斐波那契数列为例，这个题很经典了，递归和dp的教学例题，也是家常便饭。

function fib(num){
   console.log(i++);
   if(num === 1  || num === 2){
     return 1
   }
   else{
     return fib(num-1) + fib(num-2);
   }
}

最普通的递归存在大量的重复计算，所以最优解是使用动态规划来做，用空间换时间

function fib(num){
   const dp = new Array(num + 1);
   dp[1] = 1;
   dp[2] = 1;
   for(let i = 3;i<n;i++){
       dp[i] = dp[i-1] + dp[i-2];
   }
   return dp[num];
}

在很多情况下，递归比dp更容易写出来，如果你恰巧想用递归来解决问题，采用缓存来递归剪枝也可以得到最优解。

恰巧前端非常多的与缓存打交道，也希望你在以下这些递归剪枝方法中，掌握缓存——这个每个JSer的必修课。

闭包缓存

写递归的时候往往需要一个全局变量来辅助，这个变量大多数的情况下就是缓存

const m = Object.create(null); //使用全局变量做存储
function fib(num){
    if(m[num]){                //开头取
        return m[num];
    }
    if(num === 1  || num === 2){
       return 1;
    }
    else
        return m[num] = fib(num-1) + fib(num-2); //结尾存
}

全局变量造成全局污染是我们不想见到的，我们更希望这个递归函数具备独立解决问题的能力，

所以我会采用函数嵌套的方式，将这个变量塞到里面。

function fib(num){
   const m = Object.create(null);
   function _fib(num){  
     if(m[num]){
       return m[num];
     }
     if(num === 1  || num === 2){
       return 1
     }
     else{  
       return m[num] = _fib(num-1) + _fib(num-2);
     }
   }
   return _fib(num);
}

参数默认值,尾递归

用于区分第一次调用，和后续调用，使用参数默认值的方式也是一种常见方式。

 function fib(num,m = Object.create(null)){ //第一次使用的时候是1个参数 后续都是2个参数
   if(m[num]) return m[num];
   let res;
   if(num === 1  || num === 2){
     return 1;
   }
   else{
     if(m[num]){
         return m[num];
       }
       else
         return m[num] = _fib(num-1) + _fib(num-2);
   }
} 
fib(5); //5

自记忆化函数memoization

《JavaScript忍者秘籍》中有写道，使用js的函数对象做缓存。

JS中，函数与对象的区别，只有函数多一个 invokable 属性，表示其是可调用的，利用该特性，可以在函数属性上做缓存。

不涉及到随机数、网络请求等，一种自变量（入参），往往只对应着一个（返回值）。

function fib(num){
  fib.m = fib.m || Object.create(null);
  if(fib.m[num]) return fib.m[num];

  
  if(num === 1  || num === 2){
    return 1;
  }
  else
    return fib.m[num] = fib(num-1) + fib(num-2);
  }
}

链接: https://fly63.com/article/detial/11349