# 11.递归：求解汉诺塔问题
不论是数据结构还是算法思维，他们的目标都是降低时间复杂度，数据结构是从数据组织形式的角度达成这个目标，而算法思维是从数据处理的思路上去达成这个目标
举例来说，虽然选择了一个高效率的数据结构去处理问题，但是如果数据处理的逻辑上出现缺陷，仍会产生很多无效计算，造成时间浪费
# 11-1 什么是递归
在数学与计算机科学中，递归是指在函数的定义中使用函数自身的方法，直观上来看，就是某个函数调用自己
递归有两层含义
- 递归问题必须可以分解为若干个规模小、与原问题形式相同的子问题；并且这些子问题可以用完全相同的解题思路来解决
- 递归问题的演化过程是一个对原问题从大到小进行拆解的过程，并且会有一个明确的终点(临界点)；一旦原问题达到这个临界点，就不用再往更小的问题拆解了。最后，从这个临界点开始，把小问题的答案按照原路返回，原问题得以解决
简言之，递归的基本思想就是把规模大的问题转化为规模小的相同的子问题来解决。因为大问题小问题的解决方法是同一个方法，这就产生了函数调用它自身的情况，这也是递归的定义所在。
格外注意的是，这个解决问题的函数必须有明确的结束条件，否则就无导致递归的情况，总结起来：递归的实现包含了两个部分，一个是递归主题，另一个是终止条件
# 11-2 递归的算法思想
递归的数学模型其实就是数学归纳法，这个证明方法就是我们高中时期经常解决的数列问题
一个常见的题目是：证明当n等于任意一个自然数时某命题成立。
采用数学归纳法，证明分为以下两个步骤
- 1.证明当n = 1 命题成立
- 2.假设n=m命题成立，那么尝试推导出n = m + 1时，命题也成立
与数学归纳法类似，当采用递归算法解决问题时，我们也需要围绕这两个步骤去做文章
- 1.当你面对一个大规模问题时，如何把它分解为几个小规模的同样问题
- 2.当你把问题通过多轮分解后，最终的结果，也就是终止条件如何定义
所以当一个问题同时满足以下2个条件时，就可以使用递归方法求解
- 可以拆解为除了数据闺蜜外，求解思路完全相同的子问题
- 存在终止条件
在树中的任意结点来说，先中序遍历它的左子树，然后打印这个结点，最后中序遍历它的右子树
当某个结点没有左子树和右子树时，则直接打印结点，完成终止；所以树的中序遍历完全可以通过递归实现
//中序遍历
function inOrderTraverse(Node node){
if(node == null){return};
inOrderTraverse(node.left)
document.write(node.data + '')
inOrderTraverse(node.right)
}
以上就是递归的算法思想，写出递归代码的管家在于，写出递推公式和找出终止条件
也就是说我们需要：先将大问题分解成小问题的规律，并基于此写出递推公式；然后找出终止条件，就是但找到最简单的问题时，如何写出答案；最终将递推公式和终止条件翻译成实际代码
# 11-3 递归的案例
汉诺塔问题：大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上，并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘
我们把这个问题抽象为一个数学问题：从左到右有x,y,z三根柱子，其中x柱子上面有从小叠到大的n个圆盘。现要求将x柱子上的圆盘移动到z柱子上去，要求是每次只能移动一个盘子，且大盘子不能被放在小盘子上面，求移动步骤。
我们可以将这个大问题拆解为3个小问题
- 1.把从小到大的n-1个盘子，从x移动到y
- 2.接着把最大的一个盘子，从x移动到z
- 3.再把从小到大的n-1个盘子，从y移动到z
首先，我们判断它是否满足递归的第一个条件：其中1和3就是汉诺塔问题，我们定义好了递归体，也就是满足了递归的第一个条件。
接下来，我们判断它是否满足终止条件：随着递归体不断缩小范围，汉诺塔问题由原来‘移动从小到大的n个盘子’，缩小为‘移动从小到大的n-1个盘子’.移动从小到大的1个盘子，就是最小的盘子，根据规则可以发现，最小的盘子，是可以自由移动的，因此，递归的第二个条件，终止条件也是满足的。
我们定义汉诺塔的递归函数为hanoi(),这个函数的输入参数包含了：
- 3根柱子的标记x,y,z
- 等待移动的盘子数量
具体代码如下：
- 1.把从小到大的n-1个盘子从x移动到y,那么代码就是hanoi(n-1,x,y,z)
- 2.再把最大的一个盘子从x移动到z,那么直接完成一次移动的动作就可以了
- 3.再把从小到大的n-1个盘子从y移动到z,那么代码就是hanio(n-1,y,x,z).对于终止条件这需要判断n的大小，如果n等于1，那么同样直接移动就可以了
function main(String[] args){
let x = 'x';
let y = 'y';
let z = 'z';
hanio(3,x,y,z)
};
function hanoi(n,x,y,z){
if(n<1){
document.write('汉诺塔车层数不能小于1')
}else if(n == 1){
document.write(`移动：${x}->${z}`);
return;
}else{
hanio(n-1,x,z,y);
document.write(`移动：${x}->${z}`);
hanio(n-1,y,x,z)
}
}
我们以n=3为例，执行一下这段代码：
最终梳理一下，代码执行结果就是：
移动: x->z
移动: x->y
移动: z->y
移动: x->z
移动: y->x
移动: y->z
移动: x->z
抛开用于处理输入异常的代码部分不谈，它的代码包含了两个部分
- 1.终止条件，即如何处理小规模的问题，实现的代码量一定是很少的
- 2.递归体，即大问题向小问题分解的过程，实现的代码量也不会太多
所以，一个复杂问题的递归实现，通常代码量都不回太多
# 11-4 总结
递归的核心思想是把规模大的问题转化为规模小的相似的子问题来解决
- 在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数调用它自身的情况
- 这个解决问题的函数必须有明显的结束条件，这样就不会产生无限递归的情况
- 递归有很多使用的地方，例如：分治策略，快速排序等