学习笔记
-
首先规定递归什么时候结束，一定要限制条件，不能无限循环
-
递归的执行逻辑，当前层的执行逻辑，即重复性思维，重复性处理，找相似性
-
递归调用，层数加1，进入下一层
-
最后清除，如果有涉及到外部逻辑的
func recursion(level int, param1, param2 interface{}) {
// recursion terminator递归跳出条件
if level > MAX_LEVEL {
process_result
return
}
// process logic in current level 当前层的执行逻辑
process(level, data...)
// drill down递归调用
recursion(level + 1, p1, ...)
// reverse the current level status if neede 清除收尾
}
1.递归要找到重复子问题，不要人肉递归
2.一定注意递归终止条件
3.递归属于后进先出（与栈，深度优先遍历类似）
1.分治是将递归过程中的问题分步骤解决，每一步骤单独递归，最终得到结果
func recursion(level int, param1, param2 interface{}) {
// recursion terminator递归跳出条件
if level > MAX_LEVEL {
process_result
return
}
// 分治处理当前层逻辑
for {
//
process(...)
// drill down递归调用
recursion(...)
}
// reverse the current level status if neede 清除收尾
}
1.回溯采用试错的思想，分布解决，达到某种特定条件，或者是错误结果，则进行回溯，要有一个不断变化的变量，递归下一层改变，回溯上一层重置
2.递归过程中是一直向深层递归，处理完某种特定条件之后，返回当前层，回到上一层
3.对于当前层的处理进行回溯，回到上一层的状态，进行状态重置
4.在上一层做相应处理，通过分治，走下一种情况去解决，进入到另一种情况下一层，继续处理
5.重复4步骤，知道递归完毕
例如: 组合，全排列等题
1.通过递归往数组里添加数字，直到这个数组，满足结果，添加进最终结果，这个数组就是不断变化的变量
2.然后回溯，将状态回到上一层，再对上一层的分治的第二种情况，继续向下递归，然后回溯，重复步骤
3.区别在于分治时候的逻辑不一样，组合是依次遍历+1，所以不会加入重复的， 全排列是全遍历，要对于已加入的数字进行过滤
由于回溯相当于遍历，所以时间复杂度会比较高，通过特定条件进行剪枝，跳过一些情况，可以降低复杂度
比如全排列2的排序操作，通过排序预处理，针对已经加入，或者重复的进行跳过，达到剪枝，减少递归
时间复杂度： O(N×N!) 空间复杂度： O(N×N!)
1.为什么要进行回溯，不回溯的话也可以解决问题，则需要在每一层递归的时候，创建新的变量来处理问题，消耗比较大
2.回溯则是用一个变化的变量，进行修改状态，重置状态，不用创建变量
3.回溯问题思考： 1.如何产生分支，如何进行下次递归，递归树是怎样的 2.解在哪里，是在叶子节点，还是路径，还是非叶子节点，如何得到解 3.哪些情况不需要解，如何过滤掉这些解，如何剪枝，如何避免重复
func recursion(level int, param1, param2 interface{}) {
// 得到解，解的条件
terminator(...) {
return
}
// 分治处理
for {
// 剪枝判断，剪枝过滤，减少递归
fix(...)
// 得到解的过程，当前层处理逻辑，变化变量的处理
process(...)
// 进入下一层，变化的变量传入下一层
recursion(...)
// 回溯，回溯变化的变量，回到上一层之后的处理
back()
}
}