JavaScript中關(guān)于遞歸與回溯的實例詳解

更新時間：2022年07月27日 16:22:27 作者：迷途小羔羊

這篇文章主要將為大家介紹一下JavaScript中遞歸與回溯的原理及使用，文中通過一些例題進(jìn)行了詳細(xì)介紹，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下

何為遞歸

遞歸作為一種算法在程序設(shè)計語言中廣泛應(yīng)用。一個過程或函數(shù)在其定義或說明中有直接或間接調(diào)用自身的一種方法，它通常把一個大型復(fù)雜的問題層層轉(zhuǎn)化為一個與原問題相似的規(guī)模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復(fù)計算，大大地減少了程序的代碼量。遞歸的能力在于用有限的語句來定義對象的無限集合。需要注意的是，遞歸必須要用邊界條件，否則很容易導(dǎo)致死循環(huán)

構(gòu)成遞歸條件

子問題須與原始問題為同樣的事，且更為簡單
不能無限制地調(diào)用本身，須有個出口，化簡為非遞歸狀況處理

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

問題一： 假設(shè)我們需要求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

這樣的代碼是不滿足于遞歸中，直接或者間接調(diào)用本身的定義。那么如何變成遞歸版本呢？(任何的循環(huán)，都可以寫成遞歸)

尋找相同的子問題該題目相同的子問題很明顯是sum+=i，該過程是重復(fù)調(diào)用的過程。
尋找終止條件尋找遞歸的終止條件，該問題的終止條件是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

關(guān)于回溯

遞歸一定伴隨著回溯，那么什么是回溯呢？以上面的代碼為例子，我們分別在這兩處地方輸出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輸出，這就說明了一個很重要的知識點(diǎn)，遞歸函數(shù)是類似一個棧迭代的過程，它的值輸出的順序為先進(jìn)后出。通俗一點(diǎn)說，遞歸函數(shù)后面的參數(shù)，會反轉(zhuǎn)輸出。

要想理解回溯的含義，最為經(jīng)典的還是二叉樹的遍歷。二叉樹的遍歷，又分為前序遍歷，中序遍歷，后序遍歷，分別通過代碼來感受一下這三種遍歷的方式。前序遍歷

// 基本結(jié)構(gòu)
 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

后續(xù)遍歷

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

在寫遞歸的時候，時刻都要注意邊界，以上場景的邊界，則是找不到節(jié)點(diǎn)（節(jié)點(diǎn)為null）的時候，就退出。

通過輸出的結(jié)果可以得知以下規(guī)律：

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

而實現(xiàn)該規(guī)律的主要依據(jù)，是通過遞歸的回溯導(dǎo)致，我們以中序遍歷為例子：

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

當(dāng)?shù)谝粋€dfs(root.left)遞歸結(jié)束后，就會彈出'1'的節(jié)點(diǎn)，然后就進(jìn)了dfs(root.right)的節(jié)點(diǎn)，發(fā)現(xiàn)是個null，說明這個dfs(root.right)遞歸結(jié)束，那么此時則回到了'4'的節(jié)點(diǎn)，然后就進(jìn)入了dfs(root.right)節(jié)點(diǎn)...

實際業(yè)務(wù)

二叉樹的遍歷，其實類比于我們常見操作菜單樹，或著樹形結(jié)構(gòu)的操作...

let tree = [
  {
    id: '1',
    title: '節(jié)點(diǎn)1',
    children: [
      {
        id: '1-1',
        title: '節(jié)點(diǎn)1-1'
      },
      {
        id: '1-2',
        title: '節(jié)點(diǎn)1-2'
      }
    ]
  },
  {
    id: '2',
    title: '節(jié)點(diǎn)2',
    children: [
      {
        id: '2-1',
        title: '節(jié)點(diǎn)2-1'
      }
    ]
  }
]

當(dāng)我們要尋找遍歷每個節(jié)點(diǎn)的時候，同樣需要注意邊界，當(dāng)我們操作的數(shù)據(jù)沒有的時候或者不存在的時候，則退出當(dāng)次遍歷。

 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) //  ['節(jié)點(diǎn)1-1', '節(jié)點(diǎn)1-2', '節(jié)點(diǎn)2-1']
          }
        }
      }
      dfs(tree)
      return res
    }

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

 const tree = [
      {
        id: '1',
        title: '節(jié)點(diǎn)1',
        children: [
          {
            id: '1-1',
            title: '節(jié)點(diǎn)1-1'
          },
          {
            id: '1-2',
            title: '節(jié)點(diǎn)1-2'
          }
        ]
      },
      {
        id: '2',
        title: '節(jié)點(diǎn)2',
        children: [
          {
            id: '2-1',
            title: '節(jié)點(diǎn)2-1',
            children: [
              {
                id: '2-1-1',
                title: '節(jié)點(diǎn)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上的排列組合問題來進(jìn)行討論。

組合問題

經(jīng)典的組合問題

以上面題目為例子，從1-4(n)的數(shù)字中，排列2(k)個數(shù)的組合。解這個題目，可以使用暴力的做法，嵌套for循環(huán)來完成該功能。

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]

細(xì)心朋友就會發(fā)現(xiàn)，它嵌套for次數(shù)則是等于它排列(k)的次數(shù)，那么我假如k的次數(shù)是10，或者20，那么豈不是要嵌套10個或者20個for循環(huán)。這套代碼寫下來，估計是個人都會暈了。在以上代碼塊中也可以發(fā)現(xiàn)重復(fù)的子問題也就是for循環(huán)，它想要的結(jié)果則為當(dāng)我們找個了k個數(shù)的時候就停止。那么我們可以嘗試通過遞歸來解決該問題（遞歸for循環(huán)），但是這樣的過程還是很抽象的，需要借助圖例理解。（任何的組合問題，都可以理解成為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
    }

當(dāng)我們選擇到了[1,2]之后，則需要回到1的位置，因為這個時候需要選擇3選項，形成[1,3]，那么回到'1'的操作，就類似于二叉樹遍歷回到父節(jié)點(diǎn)的操作，如果此時我們不操作，path.pop()，那么此時就會形成了[1,2,3]，這樣的結(jié)果明顯不是我們想要，所以在操作push "3"的過程，需要先把2給pop掉。而遞歸的終止條件則為當(dāng)路徑的長度等于k的時候則退出。另外在函數(shù)體中，還發(fā)現(xiàn)了startIndex的存在，這個是作為橫向for循環(huán)開始的位置，我們結(jié)合上面兩個for循環(huán)的代碼，是不是發(fā)現(xiàn)了j = i + 1的操作，而這個startIndex則是還原了這個操作而已。

到此這篇關(guān)于JavaScript中關(guān)于遞歸與回溯的實例詳解的文章就介紹到這了,更多相關(guān)JavaScript遞歸回溯內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: