递归小结（一）

摘要：感悟将递归当作一种类似的控制结构，通过迭代求解问题，递归通过分治求解问题。递归解决问题的环节是明确简单情形明确相同形式的子问题。杨辉三角代码分析简单情形，可以理解为递归的终止条件，简单情形里将不递归调用或者理解为无法用递归解决的情形。

将递归当作一种类似for/while的控制结构，for/while 通过迭代求解问题，递归通过分治求解问题。
递归是这样解决问题的。
首先，这个问题存在简单情形。所谓简单情形，是指在该情形下问题不可再分割，同时这个情形下的答案显而易见。此外，简单情形还控制了解决问题的边界（具体表现在于函数不再被递归调用）。举例：

求阶乘时，n为0的情形，此时问题的解为1。至此函数不再递归调用去求解n为-1的情形。

求斐波那契数列时，n为0或1的情形，此时问题的解为n

求杨辉三角时，k为0或k为n的情形，此时问题的解为1。至此函数不再递归调用去求解k为-1或k大于n的情形。

其次，基于简单情形下的答案，可以推导出其他情形下的答案。对子问题的答案进行组织，可以求解出父问题。非简单情形下的子问题与父问题有着相同的形式。

求汉诺塔问题时，首先知道如何移动1只盘子，再知道如何通过移动1只盘子来解决移动2只盘子的问题，依此类推，就可以解决n中盘子移动的问题。

面对一个问题，思考求解决过程，发现问题可以分解成相同形式的子问题，组织子问题的答案可以求得父问题，那么可以考虑递归。递归解决问题的环节是：

明确简单情形

明确相同形式的子问题。求解父问题最终变成求解子问题，求解子问题最终变成求解简单情形

组织子问题的解去求解父问题

例如，回文探测中，问题是判断字符串是否回文。

简单情形是字符串的长度为0或1的时候，以及字符串首尾不相同的情形。

相同形式的子问题是判断缩短后的字符串是否回文。

解决父问题的策略是，先判断首尾字符是否相同，若相同，去掉首尾，判断缩短后的字符串是否回文。

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

简单情形是找到字符串的位置，或遍历完都没找到。

相同形式的子问题是查找指定字符串的位置，缩小查找范围。

解决父问题的策略是，先判断是否遍历完，是否是范围中的中间位置，若都不是，根据大小，重新划分搜索范围。

如何将问题分解成相同形式的子问题，并通过组织子问题的解去解决父问题是难点。
递归问题与排列问题。递归问题解决排列问题的特点是一个一个来。在砝码问题，字符串排列或是寻找子集的问题中，无论是砝码的数量还是字符串的长度都是有限的，所以解决问题的思路是元素一个一个地处理。
砝码问题本质是一个排列问题，只是在产生每一种组合的同时，判断该组合是否满足要求，若符合则问题得到解答。砝码问题的求解思路是每一个砝码，有三种处理策略。假设存在砝码ABCD，所有的组合方式等于砝码BCD的每一种组合方式分别加上砝码A的三种处理方式。这个寻找子集的策略相似，只不过寻找子集中，每个元素只有有和无，两种状态。
字符串排列中，通过逐步固定头部，产生所有排列。

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

其计算过程就是一颗二叉树
这个递归有值得优化的地方，将在后面的文章里分析。

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

假设有个函数能将n个盘子从x移动到y，通过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) // 访问节点（打印节点的值）
  root.left && preOrderTraverse(root.left) // 若节点的左子树存在，则遍历节点的左子树
  root.right && preOrderTraverse(root.right) // 若节点的右子树存在，则遍历节点的右子树
}
preOrderTraverse(root)

和汉诺塔问题一样，这段递归中也没有用到return。在这两个问题中，子问题中的操作构成了父问题所期待的操作。它们并不需要子问题去求出某个数值。

回文是一种字符串，其正向或反向读都是一样的。
「简单情形」，空字符串或者长度为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「不再用递归的时候」
找到或遍历完都没找到
「用子问题的解来解决父问题」，在整个数组长度里查找特定元素

元素在数组的中间位置，返回位置

元素大于处于数组中间位置的元素，在新的范围内查找特定元素

元素小于处于数组中间位置的元素，在新的范围内查找特定元素

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章