来源 | http://www.fly63.com

 
   
   
 

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

 
   
   
 

  
    
    
  
 
   
 
   
 
   
 
   
 
   
 
   
 
   
 
   
 
   
 
  
  
    
    
  
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); }}
 
   
   
 

本文完~

学习更多技能

web前端开发

一个以前端开发/网页设计/网站制作为主的知识技能学习平台，主要分享HTML/CSS/JavaScript/VueJS/ReactJS等前端开发与设计所需要的知识与技能，我们坚持每天学习一点点，每天进步一点点，关注我们，我们一起学习进步。

122篇原创内容

Official Account