递归
1 何谓递归？
重复是许多算法的一个特性，两种问题的处理方法可以求解，被称为迭代和递归。
迭代：是大家所熟悉的循环语句，不管是for， while， 还是do。循环中都会有需要重复执行的语句，以及控制重复次数的机制。迭代提供了解决一种重复性过程的直接而有效的方法。
递归：有些递归求解的方法可能是最佳方案，有些因为低效而全然不应该使用。
在解决一个问题时，更小的问题除了问题规模以外，其他的方面都是一样的。这种特殊情况的处理方式就是递归。那么问题需要解决的就是一个规模更小而其他方面与原问题一样的问题。如何用另一个问题替代原问题，并得到最终解呢？
递归成功的关键之一就是，最终稿到达一个其解已知的小规模问题，该小规模问题的解或者是显然易见，或者是已知的。求得小规模的解后，通常是原来问题的一部分，这部分再与其他部分解结合在一起，组成规模更大的问题的解
总结
递归是一种问题的求解方式，即将一个问题分解成为诺干相似但是规模更小的问题。
调用自身的方法为递归方法，这个调用就成为递归调用
1.2跟踪递归方法
java会记录该方法的执行状态，包括其形参和局部变量的值以及当前指令的位置，每一个记录被称为活动记录，提供了对方法执行期间的一个活动快照。这些记录被存在一个栈的ADT里面。当前执行的方法位于栈顶。
所以递归方法可能造成栈溢出的错误。
递归方法本身没有什么缺陷的，但是在现代的计算机系统中，执行递归的方法的方式是栈，所以对于很大的n时，很可能造成栈溢出。
2 设计递归方法
2.1首先得思考是否能够递归实现：
- 什么样的规模更小但是实质是相同的问题，其解与直接得出的部分解一起可以构成原问题的解
- 解的哪一部分可以直接得出
- 整个过程什么时候结束？-->相同实质的问题什么时候有已知解-->是否达到这个小规模或者是基本情况
2.2具体的设计方法：
- 方法必须传入一个值，这个值是用来控制递归的过程
- 方法的定义需要包括一个逻辑，方法必须以这个输入值作为导致不同情况的参数，逻辑一般是if或者是while的
- 其中一个或者多个情况是不需要递归的解，这样的情况是基本情况或者是终止情况
- 其中一个或者是多个必须包含对方法的递归调用，这些递归在某种意义上通过“更小的值”或者是“更小的任务”推进
3 常见的递归demo
熟记这几个demo，是后序高级排序算法会经常用到的
3.1 递归处理数组
3.1.1遍历数组
思路分析：
首先思考是否具备递归的条件：根据2.1的思考步骤，
是否有更小的又实质相同的问题？要遍历整个list，那么分成小问题，就是每次要遍历第一个数字。这就是递归的方法
哪一部分可以直接得到？第一个数
代码的设计：
递归的结构：遍历数组的就是每次读取一个list的第一个
终止的条件：达到数组的尾端，就是star<end（这个条件是因为在数组中是以0开始的，所以最后一个元素的位置是end-1）
控制方法推进的条件：读取完一个数字就把star+1
方法的设计：传入参数为，一个数组还有遍历数组的起点和终点
/**
* 递归遍历一个数组
* star : 开始遍历的数字，从1开始
*/
public static void displayArrayByRecursion(int[] list, int start, int end) {
// 这是更小的但是实质又是相同的步骤
System.out.print(list[start - 1] + " ");
// 这里是控制递归的结束语句
if (start < end) {
// 这里的star+1 是推进代码方法的进程
displayArrayByRecursion(list, start + 1, end);
}
}
