遞歸小結(jié)（一）

myeveryheart 發(fā)布于2019-08-21 17:16 / 2767人閱讀

摘要：感悟?qū)⑦f歸當(dāng)作一種類似的控制結(jié)構(gòu)，通過迭代求解問題，遞歸通過分治求解問題。遞歸解決問題的環(huán)節(jié)是明確簡單情形明確相同形式的子問題。楊輝三角代碼分析簡單情形，可以理解為遞歸的終止條件，簡單情形里將不遞歸調(diào)用或者理解為無法用遞歸解決的情形。

感悟

將遞歸當(dāng)作一種類似for/while的控制結(jié)構(gòu)，for/while 通過迭代求解問題，遞歸通過分治求解問題。
遞歸是這樣解決問題的。
首先，這個(gè)問題存在簡單情形。所謂簡單情形，是指在該情形下問題不可再分割，同時(shí)這個(gè)情形下的答案顯而易見。此外，簡單情形還控制了解決問題的邊界（具體表現(xiàn)在于函數(shù)不再被遞歸調(diào)用）。舉例：

求階乘時(shí)，n為0的情形，此時(shí)問題的解為1。至此函數(shù)不再遞歸調(diào)用去求解n為-1的情形。

求斐波那契數(shù)列時(shí)，n為0或1的情形，此時(shí)問題的解為n

求楊輝三角時(shí)，k為0或k為n的情形，此時(shí)問題的解為1。至此函數(shù)不再遞歸調(diào)用去求解k為-1或k大于n的情形。

其次，基于簡單情形下的答案，可以推導(dǎo)出其他情形下的答案。對子問題的答案進(jìn)行組織，可以求解出父問題。非簡單情形下的子問題與父問題有著相同的形式。

求漢諾塔問題時(shí)，首先知道如何移動1只盤子，再知道如何通過移動1只盤子來解決移動2只盤子的問題，依此類推，就可以解決n中盤子移動的問題。

面對一個(gè)問題，思考求解決過程，發(fā)現(xiàn)問題可以分解成相同形式的子問題，組織子問題的答案可以求得父問題，那么可以考慮遞歸。遞歸解決問題的環(huán)節(jié)是：

明確簡單情形

明確相同形式的子問題。求解父問題最終變成求解子問題，求解子問題最終變成求解簡單情形

組織子問題的解去求解父問題

例如，回文探測中，問題是判斷字符串是否回文。

簡單情形是字符串的長度為0或1的時(shí)候，以及字符串首尾不相同的情形。

相同形式的子問題是判斷縮短后的字符串是否回文。

解決父問題的策略是，先判斷首尾字符是否相同，若相同，去掉首尾，判斷縮短后的字符串是否回文。

例如，二分查找中，問題是查找指定字符串的位置。

簡單情形是找到字符串的位置，或遍歷完都沒找到。

相同形式的子問題是查找指定字符串的位置，縮小查找范圍。

解決父問題的策略是，先判斷是否遍歷完，是否是范圍中的中間位置，若都不是，根據(jù)大小，重新劃分搜索范圍。

如何將問題分解成相同形式的子問題，并通過組織子問題的解去解決父問題是難點(diǎn)。
遞歸問題與排列問題。遞歸問題解決排列問題的特點(diǎn)是一個(gè)一個(gè)來。在砝碼問題，字符串排列或是尋找子集的問題中，無論是砝碼的數(shù)量還是字符串的長度都是有限的，所以解決問題的思路是元素一個(gè)一個(gè)地處理。
砝碼問題本質(zhì)是一個(gè)排列問題，只是在產(chǎn)生每一種組合的同時(shí)，判斷該組合是否滿足要求，若符合則問題得到解答。砝碼問題的求解思路是每一個(gè)砝碼，有三種處理策略。假設(shè)存在砝碼ABCD，所有的組合方式等于砝碼BCD的每一種組合方式分別加上砝碼A的三種處理方式。這個(gè)尋找子集的策略相似，只不過尋找子集中，每個(gè)元素只有有和無，兩種狀態(tài)。
字符串排列中，通過逐步固定頭部，產(chǎn)生所有排列。

范式

if(簡單情形){
  簡單情形下問題的解
}else{
  將問題變成相同形式的子問題
  遞歸調(diào)用
  用子問題的解來解決原始問題
}

階乘 n! 分析

其中，1, n=0是簡單情形，factorial(n-1)是與factorial(n)相同形式的子問題，而factorail(n-1)*n是factorial(n)的解。用子問題的解來解決原始問題

代碼

const factorial = n => {
  if (n === 0) {
    return 1
  } else {
    let subProblemAnswer = factorial(n - 1)
    let answer = n * subProblemAnswer
    return answer
  }
}

console.log(factorial(4))  // 24

斐波那契序列

const fibonacci = n => {
  if(n < 2){
    return n
  }else{
    return fibonacci(n-1) + fibonacci(n-2) // 子問題的解解決父問題
  }
}

console.log(fibonacci(5)) // 5

其計(jì)算過程就是一顆二叉樹
這個(gè)遞歸有值得優(yōu)化的地方，將在后面的文章里分析。

楊輝三角 代碼

const C = (n, k) => {
  if (k === 0) {
    return 1
  } else if (k === n) {
    return 1
  } else {
    return C(n - 1, k - 1) + C(n - 1, k)
  }
}

console.log(C(6, 2)) // 15

分析

「簡單情形」，可以理解為遞歸的終止條件，簡單情形里將不遞歸調(diào)用；或者理解為無法用遞歸解決的情形。

漢諾塔 分析

假設(shè)有塔A、B、C，如何將A塔上的n個(gè)圓盤移動到B塔上，每次只能移動一只盤，在移動過程中，保持大盤在下，小盤在上。

「簡單情形」，n=1，只需要移動一只盤子，從A到B
「用子問題的解來解決父問題」，從A移動n個(gè)圓盤到B

先從A移動n-1只盤子到C

再從A移動1只盤子到B

最后從C移動n-1只盤子到B

假設(shè)有個(gè)函數(shù)能將n個(gè)盤子從x移動到y(tǒng)，通過z

代碼

const hanoiTower = (n, from, to, temp) => {
  if (n === 1) {
    console.log(`${from}->${to}`)
  } else {
    hanoiTower(n - 1, from, temp, to)
    hanoiTower(1, from, to, temp)
    hanoiTower(n - 1, temp, to, from)
  }
}

hanoiTower(3, "A", "B", "C")

這段代碼沒有用到return

二叉樹的遍歷

const preOrderTraverse = root => {
  console.log(root.value) // 訪問節(jié)點(diǎn)（打印節(jié)點(diǎn)的值）
  root.left && preOrderTraverse(root.left) // 若節(jié)點(diǎn)的左子樹存在，則遍歷節(jié)點(diǎn)的左子樹
  root.right && preOrderTraverse(root.right) // 若節(jié)點(diǎn)的右子樹存在，則遍歷節(jié)點(diǎn)的右子樹
}
preOrderTraverse(root)

和漢諾塔問題一樣，這段遞歸中也沒有用到return。在這兩個(gè)問題中，子問題中的操作構(gòu)成了父問題所期待的操作。它們并不需要子問題去求出某個(gè)數(shù)值。

回文探測 分析

回文是一種字符串，其正向或反向讀都是一樣的。
「簡單情形」，空字符串或者長度為1的字符串是回文字符串。
「用子問題的解來解決父問題」，判斷一個(gè)字符串是回文

判斷字符串的首尾是否相同

若相同，判斷去除首尾的子字符串是否回文

代碼

const isPalindreme = str => {
  if (str.length < 2) {
    return true
  } else {
    if (str[0] === str[str.length - 1]) {
      return isPalindreme(str.slice(1, -1))
    } else {
      return false
    }
  }
}

console.log(isPalindreme("abcdedcba"))

二分查找 分析

「簡單情形」or「不再用遞歸的時(shí)候」
找到或遍歷完都沒找到
「用子問題的解來解決父問題」，在整個(gè)數(shù)組長度里查找特定元素

元素在數(shù)組的中間位置，返回位置

元素大于處于數(shù)組中間位置的元素，在新的范圍內(nèi)查找特定元素

元素小于處于數(shù)組中間位置的元素，在新的范圍內(nèi)查找特定元素

代碼

console.log(function (arr, key) {
  const binarySearch = (low, high) => {
    if (low > high) { // 遍歷完都沒找到
      return -1
    }
    let mid = Math.floor((low + high) / 2)
    if (arr[mid] === key) { // 找到
      return mid
    } else if (key > arr[mid]) {
      return binarySearch(mid + 1, high)
    } else {
      return binarySearch(low, high - 1)
    }
  }
  return binarySearch(0, arr.length - 1)
}([1, 2, 3, 4], 4))

砝碼問題 分析

確定一組給定的砝碼和一個(gè)天平能否稱指定的重量，例如[1, 3]可以稱1, 2, 3, 4，但不可以稱5。
「簡單情形」or「不再用遞歸的時(shí)候」
找到組合稱出指定的重量或用盡所有砝碼的組合都未能稱出
假設(shè)共有n個(gè)砝碼，每個(gè)砝碼可以放在左邊或右邊或不用，3種擺放方式。假設(shè)n-1個(gè)砝碼共有m種擺放方式，那么n個(gè)砝碼共有3m種擺放方式。
「用子問題的解來解決父問題」，判斷使用當(dāng)前砝碼能否使天平平衡

將砝碼放在左邊，判斷天平是否平衡

若否，將砝碼放在右邊，判斷天平是否平衡

若否，嘗試將砝碼放在左邊，判斷使用下一個(gè)砝碼能否使天平平衡

若否，嘗試將砝碼放在右邊，判斷使用下一個(gè)砝碼能否使天平平衡

若否，不放該砝碼，判斷使用下一個(gè)砝碼能否使天平平衡

代碼

const main = (arr, target) => {
  const isMeasureable = (i, left, right) => {
    if (!arr[i]) {
      return false
    }
    let weight = arr[i]
    if (left + weight === right) {
      return true
    } else if (left === right + weight) {
      return true
    } else if (isMeasureable(i + 1, left + weight, right)) {
      return true
    } else if (isMeasureable(i + 1, left, right + weight)) {
      return true
    } else if (isMeasureable(i + 1, left, right)) {
      return true
    } else {
      return false
    }
  }
  console.log(isMeasureable(0, target, 0))
}

main([1, 3, 5], 10)

字符串排列 分析

列出一個(gè)字符串所有的排列組合
一個(gè)字符串"ABCDE"所有的排列組合等于

"A"+字符串"BCDE"所有的排列組合

"AB"+字符串"CDE"所有的排列組合

"AC"+字符串"BDE"所有的排列組合

"AD"+字符串"BCE"所有的排列組合

"AE"+字符串"BCD"所有的排列組合

"B"+字符串"ACDE"所有的排列組合

"C"+字符串"ABDE"所有的排列組合

"D"+字符串"ABCE"所有的排列組合

"E"+字符串"ABCD"所有的排列組合

代碼

const main = str => {
  const listPermutations = (preStr, str) => {
    if (str.length === 0) {
      console.log(preStr)
    } else {
      for (let i = 0; i < str.length; i++) {
        listPermutations(preStr + str[i], str.slice(0, i) + str.slice(i + 1))
      }
    }
  }
  listPermutations("", str)
}
main("ABCD")

解決字符串重復(fù)問題

const main = str => {
  const listPermutations = (preStr, str) => {
    if (str.length === 0) {
      console.log(preStr)
    } else {
      for (let i = 0; i < str.length; i++) {
        if(i === 0){
          listPermutations(preStr + str[i], str.slice(0, i) + str.slice(i + 1))
        }else if(str[i] !== str[i-1]){
          listPermutations(preStr + str[i], str.slice(0, i) + str.slice(i + 1))
        }
      }
    }
  }
  listPermutations("", Array.from(str).sort().join(""))
}

main("ABCD")
console.log("---------")
main("AABB")

尋找子集 分析

列出給定字符串的所有子集
「簡單情形」，字符串""的子集
「用子問題的解來解決父問題」，列出字符串"ABC"的子集

列出字符串"BC"的子集

字符串"ABC"的子集等于[字符串"BC"的子集,字符串"BC"的子集中每個(gè)元素+"A"]

代碼

const main = str => {
  const listSubsets = str => {
    if (str.length === 0) {
      return [""]
    } else {
      let arr = listSubsets(str.slice(1))
      let arr2 = arr.map(i => {
        return str[0] + i
      })
      return arr.concat(arr2)
    }
  }
  console.log(listSubsets(str))
}

main("ABC")

問題來源

程序設(shè)計(jì)抽象思想第4章第5章