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

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

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

何為遞歸

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

構(gòu)成遞歸條件

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

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

問(wèn)題一： 假設(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

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

尋找相同的子問(wèn)題該題目相同的子問(wèn)題很明顯是sum+=i，該過(guò)程是重復(fù)調(diào)用的過(guò)程。
尋找終止條件尋找遞歸的終止條件，該問(wèn)題的終止條件是i>100的情況

這兩大要素都找到了，就很容易寫(xiě)出下面的遞歸版本

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
    }

毫無(wú)疑問(wèn)，"遞歸前的n"會(huì)按照1-100輸出，而"遞歸后的n"則會(huì)100-1輸出，這就說(shuō)明了一個(gè)很重要的知識(shí)點(diǎn)，遞歸函數(shù)是類(lèi)似一個(gè)棧迭代的過(guò)程，它的值輸出的順序?yàn)橄冗M(jìn)后出。通俗一點(diǎn)說(shuō)，遞歸函數(shù)后面的參數(shù)，會(huì)反轉(zhuǎn)輸出。

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

// 基本結(jié)構(gòu)
 const treeNode = {
      val: 1,
      left: null,
      right: {
        val: 2,
        left: {
          val: 3,
          left: null,
          right: null
        },
        right: null
      }
    }

來(lái)看下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

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

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

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

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

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

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

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

二叉樹(shù)的遍歷，其實(shí)類(lèi)比于我們常見(jiàn)操作菜單樹(shù)，或著樹(shù)形結(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)我們要尋找遍歷每個(gè)節(jié)點(diǎn)的時(shí)候，同樣需要注意邊界，當(dāng)我們操作的數(shù)據(jù)沒(méi)有的時(shí)候或者不存在的時(shí)候，則退出當(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) // 開(kāi)始遞歸
          } else {
            res.push(t.title) //  ['節(jié)點(diǎn)1-1', '節(jié)點(diǎn)1-2', '節(jié)點(diǎn)2-1']
          }
        }
      }
      dfs(tree)
      return res
    }

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

 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]

其實(shí)以上核心的代碼為path.pop()，為什么需要這句代碼呢？我們可以通過(guò)leetcode上的排列組合問(wèn)題來(lái)進(jìn)行討論。

組合問(wèn)題

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

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

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

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

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

您可能感興趣的文章: