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

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

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

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

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

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

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

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

明確簡單情形

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

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

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

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

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

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

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

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

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

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

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

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

其中，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

其計算過程就是一顆二叉樹
這個遞歸有值得優(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

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

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

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

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

再從A移動1只盤子到B

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

假設有個函數(shù)能將n個盤子從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é)點（打印節(jié)點的值）
  root.left && preOrderTraverse(root.left) // 若節(jié)點的左子樹存在，則遍歷節(jié)點的左子樹
  root.right && preOrderTraverse(root.right) // 若節(jié)點的右子樹存在，則遍歷節(jié)點的右子樹
}
preOrderTraverse(root)

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

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

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

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

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ù)組長度里查找特定元素

元素在數(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))

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

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

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

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

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

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

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)

列出一個字符串所有的排列組合
一個字符串"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")

解決字符串重復問題

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"的子集中每個元素+"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")

程序設計抽象思想 第4章 第5章