函數(shù)遞歸優(yōu)化，JavaScript中應該如何寫遞歸？

點擊上方?前端Q，關注公眾號

回復加群，加入前端Q技術交流群

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

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

以最基礎的斐波那契數(shù)列為例，這個題很經(jīng)典了，遞歸和dp的教學例題，也是家常便飯。

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

最普通的遞歸存在大量的重復計算，所以，最優(yōu)解是使用動態(tài)規(guī)劃來做，用空間換時間。

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

在很多情況下，遞歸比dp更容易寫出來，如果你恰巧想用遞歸來解決問題，采用緩存來遞歸剪枝也可以得到最優(yōu)解。

恰巧前端非常多的與緩存打交道，也希望你在以下這些遞歸剪枝方法中，掌握緩存——這個每個JSer的必修課。

閉包緩存

寫遞歸的時候往往需要一個全局變量來輔助，這個變量大多數(shù)的情況下就是緩存

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); //結尾存}

全局變量造成全局污染是我們不想見到的，我們更希望這個遞歸函數(shù)具備獨立解決問題的能力。

所以我會采用函數(shù)嵌套的方式，將這個變量塞到里面。

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

參數(shù)默認值，尾遞歸

用于區(qū)分第一次調(diào)用，和后續(xù)調(diào)用，使用參數(shù)默認值的方式也是一種常見方式。

 function fib(num,m = Object.create(null)){ //第一次使用的時候是1個參數(shù) 后續(xù)都是2個參數(shù)   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

自記憶化函數(shù)memoization

《JavaScript忍者秘籍》中有寫道，使用js的函數(shù)對象做緩存。

JS中，函數(shù) 與 對象的區(qū)別，只有函數(shù)多一個 invokable 屬性，表示其是可調(diào)用的，利用該特性，可以在函數(shù)屬性上做緩存。

不涉及到隨機數(shù)、網(wǎng)絡請求等，一種自變量（入?yún)ⅲ?，往往只對應著一個（返回值）。

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

本文完~

往期推薦

大廠面試官：我理想中的前端

對話Svelte未來，Rust 編譯器？構建大型應用?

收藏！史上最全 Vue 前端代碼風格指南

最后

• 歡迎加我微信，拉你進技術群，長期交流學習...
  

• 歡迎關注「前端Q」,認真學前端，做個專業(yè)的技術人...

點個在看支持我吧