JavaScript中關於遞迴與回溯的範例詳解

2022-07-27 22:02:41

何為遞迴

遞迴作為一種演演算法在程式設計語言中廣泛應用。一個過程或函數在其定義或說明中有直接或間接呼叫自身的一種方法，它通常把一個大型複雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞迴策略只需少量的程式就可描述出解題過程所需要的多次重複計算，大大地減少了程式的程式碼量。遞迴的能力在於用有限的語句來定義物件的無限集合。需要注意的是，遞迴必須要用邊界條件，否則很容易導致死迴圈

構成遞迴條件

子問題須與原始問題為同樣的事，且更為簡單
不能無限制地呼叫本身，須有個出口，化簡為非遞迴狀況處理

但是遞迴函數並不容易一下子就能想的出來，所以我們可以先通過一個子問題來逐步延申。

問題一： 假設我們需要求1+2+3+...+100的值，我們很容易想出下面的程式碼

 function calcNum(n) {
      let sum = 0
      for (let i = 0; i <= 100; i++) {
        sum += i
      }
      return sum
    }
    console.log(calcNum()) // 5050

這樣的程式碼是不滿足於遞迴中，直接或者間接呼叫本身的定義。那麼如何變成遞迴版本呢？(任何的迴圈，都可以寫成遞迴)

尋找相同的子問題該題目相同的子問題很明顯是sum+=i，該過程是重複呼叫的過程。
尋找終止條件尋找遞迴的終止條件，該問題的終止條件是i>100的情況

這兩大要素都找到了，就很容易寫出下面的遞迴版本

function calcNum(n) {
      let sum = 0
      function dfs(n) {
        if (n > 100) {
          return
        }
        sum += n
        n++
        dfs(n)
      }
      dfs(n)
      return sum
    }
    console.log(calcNum(1)) // 5050

關於回溯

遞迴一定伴隨著回溯，那麼什麼是回溯呢？以上面的程式碼為例子，我們分別在這兩處地方輸出n的值

function calcNum(n) {
      let sum = 0
      function dfs(n) {
        if (n > 100) {
          return
        }
        sum += n
        n++
        console.log(n, '遞迴前的n')
        dfs(n)
        console.log(n, '遞迴後的n')
      }
      dfs(n)
      return sum
    }

毫無疑問，"遞迴前的n"會按照1-100輸出，而"遞迴後的n"則會100-1輸出，這就說明了一個很重要的知識點，遞迴函數是類似一個棧迭代的過程，它的值輸出的順序為先進後出。通俗一點說，遞迴函數後面的引數，會反轉輸出。

要想理解回溯的含義，最為經典的還是二元樹的遍歷。二元樹的遍歷，又分為前序遍歷，中序遍歷，後序遍歷，分別通過程式碼來感受一下這三種遍歷的方式。前序遍歷

// 基本結構
 const treeNode = {
      val: 1,
      left: null,
      right: {
        val: 2,
        left: {
          val: 3,
          left: null,
          right: null
        },
        right: null
      }
    }

來看下leetcode 前序遍歷原題

const root = {
      val: 5,
      left: {
        val: 4,
        left: {
          val: 1,
          right: null,
          left: null
        },
        right: {
          val: 2,
          right: null,
          left: null
        }
      },
      right: {
        val: 6,
        left: {
          val: 7,
          left: null,
          right: null
        },
        right: {
          val: 8,
          left: null,
          right: null
        }
      }
    }
    function getRoot(root) {
      const res = []
      function dfs(root) {
        if (!root) {
          return
        }
        res.push(root.val)
        dfs(root.left)
        dfs(root.right)
      }
      dfs(root)
      return res
    }
    console.log(getRoot(root)) // 5 4 1 2 6 7 8

中序遍歷

function getRoot(root) {
      const res = []
      function dfs(root) {
        if (!root) {
          return
        }
        dfs(root.left)
        res.push(root.val)
        dfs(root.right)
      }
      dfs(root)
      return res
    }
    console.log(getRoot(root)) // 1 4 2 5 6 7 8

後續遍歷

function getRoot(root) {
      const res = []
      function dfs(root) {
        if (!root) {
          return
        }
        dfs(root.left)
        dfs(root.right)
        res.push(root.val)
      }
      dfs(root)
      return res
    }
    console.log(getRoot(root)) // 1 2 4 7 8 6 5

在寫遞迴的時候，時刻都要注意邊界，以上場景的邊界，則是找不到節點（節點為null）的時候，就退出。

通過輸出的結果可以得知以下規律：

前序遍歷：中左右
中序遍歷：左中右
後序遍歷：左右中

而實現該規律的主要依據，是通過遞迴的回溯導致，我們以中序遍歷為例子：

 dfs(root.left)
 res.push(root.val)
 dfs(root.right)

當第一個dfs(root.left)遞迴結束後，就會彈出'1'的節點，然後就進了dfs(root.right)的節點，發現是個null，說明這個dfs(root.right)遞迴結束，那麼此時則回到了'4'的節點，然後就進入了dfs(root.right)節點...

實際業務

二元樹的遍歷，其實類比於我們常見操作選單樹，或著樹形結構的操作...

let tree = [
  {
    id: '1',
    title: '節點1',
    children: [
      {
        id: '1-1',
        title: '節點1-1'
      },
      {
        id: '1-2',
        title: '節點1-2'
      }
    ]
  },
  {
    id: '2',
    title: '節點2',
    children: [
      {
        id: '2-1',
        title: '節點2-1'
      }
    ]
  }
]

當我們要尋找遍歷每個節點的時候，同樣需要注意邊界，當我們操作的資料沒有的時候或者不存在的時候，則退出當次遍歷。

 function getRootData(tree) {
      const res = []
      function dfs(tree) {
        if (!tree || tree.length === 0) {
          return res
        }
        for (let i = 0; i < tree.length; i++) {
          const t = tree[i]
          if (t.children && t.children.length > 0) {
            dfs(t.children) // 開始遞迴
          } else {
            res.push(t.title) //  ['節點1-1', '節點1-2', '節點2-1']
          }
        }
      }
      dfs(tree)
      return res
    }

可能有人會有疑問，這也沒有利用到回溯的操作啊，那麼我就換個場景，假如我給個你節點的id，你幫我找出他所有的父節點，那麼你可能會怎麼操作呢？

 const tree = [
      {
        id: '1',
        title: '節點1',
        children: [
          {
            id: '1-1',
            title: '節點1-1'
          },
          {
            id: '1-2',
            title: '節點1-2'
          }
        ]
      },
      {
        id: '2',
        title: '節點2',
        children: [
          {
            id: '2-1',
            title: '節點2-1',
            children: [
              {
                id: '2-1-1',
                title: '節點2-1-1'
              }
            ]
          }
        ]
      }
    ]
    function pathTree(tree, id) {
      const res = []
      function dfs(tree, path) {
        if (!tree || tree.length === 0) {
          return
        }
        for (let i = 0; i < tree.length; i++) {
          const t = tree[i]
          path.push(t.id)
          if (path.includes(id)) {
            res.push(path.slice())
          }
          if (t.children && t.children.length > 0) {
            dfs(t.children, path)
          }
          path.pop() // 路徑回溯
        }
      }
      dfs(tree, [])
      return res
    }
    console.log(pathTree(tree, '2-1-1')) // [2,2-1,2-1-1]

其實以上核心的程式碼為path.pop()，為什麼需要這句程式碼呢？我們可以通過leetcode上的排列組合問題來進行討論。

組合問題

經典的組合問題

以上面題目為例子，從1-4(n)的數位中，排列2(k)個數的組合。解這個題目，可以使用暴力的做法，巢狀for迴圈來完成該功能。

function combine(n) {
      const res = []
      for (let i = 1; i <= n; i++) {
        for (let j = i + 1; j <= n; j++) {
          res.push([i, j])
        }
      }
      return res
    }

  console.log(combine(4), 'res') // [1,2][1,3][1,4][2,3][3,4][2,4]

細心朋友就會發現，它巢狀for次數則是等於它排列(k)的次數，那麼我假如k的次數是10，或者20，那麼豈不是要巢狀10個或者20個for迴圈。這套程式碼寫下來，估計是個人都會暈了。在以上程式碼塊中也可以發現重複的子問題也就是for迴圈，它想要的結果則為當我們找個了k個數的時候就停止。那麼我們可以嘗試通過遞回來解決該問題（遞迴for迴圈），但是這樣的過程還是很抽象的，需要藉助圖例理解。（任何的組合問題，都可以理解成為n叉樹的遍歷）

 function combine(n, k) {
      const res = []
      function dfs(n, path, startIndex) {
        if (path.length === k) {
          res.push(path.slice())
          return
        }
        for (let i = startIndex; i <= n; i++) {
          path.push(i)
          dfs(n, path, i + 1)
          path.pop()
        }
      }
      dfs(n, [], 1)
      return res
    }

當我們選擇到了[1,2]之後，則需要回到1的位置，因為這個時候需要選擇3選項，形成[1,3]，那麼回到'1'的操作，就類似於二元樹遍歷回到父節點的操作，如果此時我們不操作，path.pop()，那麼此時就會形成了[1,2,3]，這樣的結果明顯不是我們想要，所以在操作push "3"的過程，需要先把2給pop掉。而遞迴的終止條件則為當路徑的長度等於k的時候則退出。另外在函數體中，還發現了startIndex的存在，這個是作為橫向for迴圈開始的位置，我們結合上面兩個for迴圈的程式碼，是不是發現了j = i + 1的操作，而這個startIndex則是還原了這個操作而已。

到此這篇關於JavaScript中關於遞迴與回溯的範例詳解的文章就介紹到這了,更多相關JavaScript遞迴回溯內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！