JavaScript中關於遞歸與回溯的實例詳解
何為遞歸
遞歸作為一種算法在程序設計語言中廣泛應用。 一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略隻需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少瞭程序的代碼量。遞歸的能力在於用有限的語句來定義對象的無限集合。需要註意的是，遞歸必須要用邊界條件，否則很容易導致死循環
構成遞歸條件
- 子問題須與原始問題為同樣的事，且更為簡單
- 不能無限制地調用本身，須有個出口，化簡為非遞歸狀況處理
但是遞歸函數並不容易一下子就能想的出來，所以我們可以先通過一個子問題來逐步延申。
問題一： 假設我們需要求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遞歸 回溯內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！
推薦閱讀：
- JavaScript前端面試扁平數據轉tree與tree數據扁平化
- C++實現LeetCode(111.二叉樹的最小深度)
- JavaScript二叉搜索樹構建操作詳解
- C++實現LeetCode(116.每個節點的右向指針)
- C++實現LeetCode(104.二叉樹的最大深度)