函數遞歸優化，JavaScript中應該如何寫遞歸？

​

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

本文完~

學習更多技能

請點選下方公衆号

​