遞歸算法

• 2021 年 5 月 3 日
• 筆記
• js, 前端, 算法

遞歸算法

1. 什麼是遞歸

   在運行過程中，自身調用自身。

   一個條件：至少應該有一個結束條件。

例子：

1. 你和你的朋友在一個地方約見面，他已經到了，你距離你們約定的地方還差100步。
   那麼最後這一百步，你肯定是需要一步一步走過去。

   那麼咱們如何用遞歸的方式來實現最後這100步呢

   示例代碼：

   function walk(step) {
       if (step == 0) {
           console.log('已經到達目的地')
       }else {
           step--
           console.log(`已經走了一步，還剩${step}步`)
           walk(step)
       }
   }
   walk(100)
   

   遞歸一般應用在什麼場景下

   在有很多層級結構，並且每個層級的結構都是大致相同的。一般情況下，前後都有依賴。

   遞歸的方式和普通的函數調用的方式，遞歸效率更低。

   所以呢，在日常的開發當中，我們不要濫用遞歸。

2. 某一個數與另外一個數之間的和怎麼遞歸實現

   示例代碼：

   // min 最小值
   // max 最大值
   
   function sum(min, max) {
      if (min == max) {
         return max
      }else {
         return min + sum(min + 1, max)
      }
   }
   
   let result = sum(1,100)
   console.log(result)
   

3. 將列表型的數據轉化成樹形數據

   示例代碼：

   export function tranListToTreeData(list, rootValue) {
    var arr = []
    list.forEach(item => {
        if (item.pid === rootValue) {
            const children = tranListToTreeData(list, item.id)
            if (children.length) {
                item.children = children
            }
            arr.push(item)
        }
   })
   return arr
   }