递归与回溯总结

递归与回溯介绍

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。

如果是线型递归，子问题直接回到父问题不需要回溯，但是如果是树型递归，父问题有很多分支，我需要从子问题回到父问题，进入另一个子问题。因此回溯是指在递归过程中，从某一分支的子问题回到父问题进入父问题的另一子问题分支，因为有时候进入第一个子问题的时候修改过一些变量，因此回溯的时候会要求改回父问题时的样子才能进入第二子问题分支。

递归模版

递归有一个三段式模版：

• 终止条件： 如果没有终止条件，递归会无限进行下去，类似死循环，因此我们要给它一个出口。
• 返回值： 进入递归函数的返回值，以及子问题返回父问题的返回值是一致的，要让子问题解决什么就返回什么。
• 本级任务： 每一级子问题都有相同的任务，完成该任务后进入子问题。树型递归还需要回溯。

经典题型

• 没有重复项数字的全排列 寻找子问题：我们可以看数组[1,2,3,4],如果遍历经过一个元素2以后，那就相当于我们确定了数组到该元素为止的前半部分，前半部分1和2的位置都不用变了，只需要对3，4进行排列，这对于后半部分而言同样是一个全排列，同样要对从每个元素开始往后交换位置，因此后面部分就是一个子问题。

  • 终止条件： 要交换位置的下标到了数组末尾，没有可交换的了，那这就构成了一个排列情况，可以加入输出数组。
  • 返回值： 每一级的子问题应该把什么东西传递给父问题呢，这个题中我们是交换数组元素位置，前面已经确定好位置的元素就是我们返还给父问题的结果，后续递归下去会逐渐把整个数组位置都确定，形成一种排列情况。
  • 本级任务： 每一级需要做的就是遍历从它开始的后续元素，每一级就与它交换一次位置。
  • 回溯： 每级的子问题处理完回到父问题要修改回父问题刚开始的状态。

• 有重复项数字的全排列 寻找子问题：每当我们选取一个数组元素以后，就确定了其位置，相当于对数组中剩下的元素进行全排列添加在该元素后面，给剩余部分进行全排列就是一个子问题。

  • 终止条件： 临时数组中选取了n个元素，已经形成了一种排列情况了，可以将其加入输出数组中。
  • 返回值： 每一层给上一层返回的就是本层级在临时数组中添加的元素，递归到末尾的时候就能添加全部元素。
  • 本级任务： 每一级都需要选择一个元素加入到临时数组末尾（遍历数组选择）。首先已经加入的元素不能再次加入了，因此我们需要使用额外的vis数组用于记录哪些位置的数字被加入了。同时为了去除重复元素的影响，如果当前的元素num[i]与同一层的前一个元素num[i-1]相同且num[i-1]已经用过了，也不需要将其纳入。
  • 回溯： 每级的子问题处理完回到父问题要修改回父问题刚开始的状态。

  

• 岛屿数量 这道题是递归的一种经典形式，矩阵的dfs（深度优先搜索）。寻找子问题：当我们遇到矩阵的某个元素为1时，首先将其置为了0，然后查看与它相邻的上下左右四个方向，如果这四个方向相邻元素为1，则进入该元素，进入该元素之后我们发现又回到了刚刚的子问题，又是把这一片相邻区域的1全部置为0。

  • 终止条件： 进入某个元素修改其值为0后，遍历四个方向发现周围都没有1，那就不用继续递归，返回即可，或者递归到矩阵边界也同样可以结束。
  • 返回值： 每一级的子问题就是把修改后的矩阵返回，因为其是函数引用，也不用管。
  • 本级任务： 对于每一级任务就是将该位置的元素置为0，然后查询与之相邻的四个方向，看看能不能进入子问题。
  • 回溯： 虽然有很多分支，但分支没有修改父问题影响子问题的值，不需要单独回溯操作。

• 字符串的排列与数组全排列没有区别，寻找子问题：每当我们选取一个字符以后，就确定了其位置，相当于对字符串中剩下的元素进行全排列添加在该元素后面，给剩余部分进行全排列就是一个子问题。

  • 终止条件： 临时字符串中选取了n个元素，已经形成了一种排列情况了，可以将其加入输出数组中。
  • 返回值： 每一层给上一层返回的就是本层级在临时字符串中添加的元素，递归到末尾的时候就能添加全部元素。
  • 本级任务： 每一级都需要选择一个元素加入到临时字符串末尾（遍历原字符串选择）。首先已经加入的元素不能再次加入了，因此我们需要使用额外的vis数组用于记录哪些位置的字符被加入了。同时为了去除重复元素的影响，如果当前的元素str[i]与同一层的前一个元素str[i-1]相同且str[i-1]已经用过了，也不需要将其纳入。
  • 回溯： 每级的子问题处理完回到父问题要修改回父问题刚开始的状态。

• 矩阵最长递增路径这道题也是矩阵的dfs。寻找子问题：我们查找递增路径的时候，每次选中路径一个点，然后找到与该点相邻的递增位置，相当于进入这个相邻的点，继续查找递增路径，这就是递归的子问题。

  • 终止条件： 进入路径最后一个点后，四个方向要么是矩阵边界，要么没有递增的位置，路径不能再增长，返回上一级。
  • 返回值： 每次返回的就是本级之后的子问题中查找到的路径长度加上本级的长度。
  • 本级任务： 每次进入一级子问题，先初始化后续路径长度为0，然后遍历四个方向（可以用数组表示，下标对数组元素的加减表示去往四个方向），进入符合不是边界且在递增的邻近位置作为子问题，查找子问题中的递增路径长度。因为有四个方向，所以最多有四种递增路径情况，因此要维护当级子问题的最大值。

• N皇后问题 寻找子问题：如果皇后出现在第一列，那么第一行的皇后位置就确定了，相当于在剩余的n-1行中找n-1个皇后的位置，这就是一个子问题。

  • 终止条件： 当最后一行都被选择了位置，说明n个皇后位置齐了，增加一种方案数返回。
  • 返回值： 每一级要将选中的位置及方案数返回。
  • 本级任务： 每一级其实就是在该行选择一列作为该行皇后的位置，遍历所有的列选择一个符合条件的位置加入数组，然后进入下一级。
  • 这里不用手动回溯，因为回到父问题选择下一分支的时候，他会自动修改数组的值，因为每一行（每级子问题）只有一个元素给它用。

  

• 括号生成 寻找子问题：相当于一共n个左括号和n个右括号，可以给我们使用。如果使用了一个左括号以后，那么还剩下n-1个左括号和n个右括号，也是将这些括号连接成一个字符串，就相当于是原问题的子问题。

  • 终止条件： 左右括号都使用了n个，将结果加入数组。
  • 返回值： 每一级向上一级返回后续组装后的字符串，即子问题中搭配出来的括号序列。
  • 本级任务： 每一级就是保证左括号还有剩余的情况下，使用一次左括号进入子问题，或者右括号还有剩余且右括号使用次数少于左括号的情况下使用一次右括号进入子问题。