算法训练营第03周学习笔记

树的数据结构基本上都是递归型的定义即泛型递归、树的递归。 1.节点和树本身、数据结构的定义就是用递归的方式进行的； 2.重复性（自相似性）二叉树以及搜索二叉树，比如二叉搜索树始终是左子树大于根节点，且根节点大于右子树的不断重复下去；树的前、中序遍历就是一个递归的函数。

递归（Recursion） 递归是通过函数体来进行循环的一种循环，这个原因是在计算机语言被创造的时候本质上就是汇编语言，其汇编的特点是没有循环嵌套这个概念/定义，而汇编使用“循环”的时候是在之前已经编写的函数/指令写在的位置，然后就不断地反复跳到之前的那段函数/指令,不断的去执行，这实际上就是所谓的递归。所以递归和循环没有特别明显边界。

递归的具体类比是要找到归去来兮的形象化思想； eg. 电影《盗梦空间》 1.递归的特点是向下进入到不同的递归层，向上又回到原来的一层，一般来说他是不能跳跃而是一层层的下去，再一层层回来。看起来具有对称性，归去来兮的状态； 2.通过一种同步的节律回到上一层，所谓的同步关系就是用参数来进行函数不同层之间的传递变量； 3.每一层的环境和周围的参数都是一份拷贝、“主函数”穿越不同层级其参数发生和携带变化；即主函数携带全局变量改变每一层递归的具体参数。

递归代码的具体实现步骤： 1.第一步定义递归终结条件；（terminator） 2.处理当前层的逻辑；（current level logic） 3.携带参数去往下一层；（drill down） 4.递归结束后要清理当前层的全局变量。（reverse）

关于递归思维的要点： 1.练习熟练后不要去用演草纸把递归的所有状态进行归档演算或者手画递归的状态树，一定要练习看到函数就直接写的状态； 2.找到最近、最简单的方法，将其拆解成可重复解决的问题（重复子问题）；因为程序指令到最后只包括if else、for、while、loop，然后就是递归调用； 3.数学归纳法思维；找最开始成立的逻辑，然后证明在有限次计算内这个逻辑都成立； 4.递归的“模板”一定要深刻记忆并熟练应用。

分治和回溯（Divide & Conquer / Backtracking）

分治和回溯是属于递归的其中一种，是递归的一个细分类、是一种特殊的递归、相对较为复制一些的递归。

用分治、回溯和递归最关键的操作就是找最近或者最优可重复的子问题，最近重复性是根据重复性的构造以及怎么分解就采用什么样的分治或者最后要回溯的办法，本质上就是递归，递归就是找最近相似重复性；所谓最优重复性就是动态规划的思想。

思考分治：什么地方是不需要划分子问题？基本上是没有。 即使自有一个子问题的阶乘的计算也是一个只有一步子问题的特殊划分；解决问题最有效的方法就是找最近/最优重复性。

递归和分治的代码也具有最近相似重复性的特点，唯一区别就是分治更复杂一些，把简单的递归分成模块化的操作，把一个个小中间的子结果组装成一个大的结果，最后返回。

回溯是采用试错的思想，尝试分步去解决同一个问题；在分步解决问题的过程中，通过尝试发现现有的分步答案不能得到有效的正确解答的时候，将取消上一步甚至上几步的计算，再通过其他的可能分步解答再次尝试寻找最近重复子问题。 回溯法通常用最简单的递归方法来实现，在反复重复上述步骤后可能出现两种情况： 1.找到一个可能存在的正确的答案； 2.在尝试了所有可能的分步方法后宣告该问题没有答案。 （在最坏的情况下，回溯法会导致复杂度为指数时间的计算。）回溯在最典型的问题是解决八皇后和数独上面的应用。

递归的简化精要是自顶向下设计，然后再自下向上回归。例如：谷歌的MapReduce的精髓做法就是自顶向下递归，即自顶向下分解的过程被称为Map，自底向上合并的过程被称为Reduce。

寻找最近重复性的原则就是用好数学归纳法，在数学和计算机上有一个非常重要的等价性原则，掌握了这个原则就可以把很多问题归结为一类问题，解决了其中一个问题，其他问题也就迎刃而解了。

PS： 递归有个最大的特点是它只关心自己的下一层，而并不关心更下面的细节；就像课程里覃超老师类比的人事管理的例子，公司的组织管理是自顶向下设计的，逐级发号命令，因此不同层级的人关心的事情不同。