递归算是一个困扰我很久的问题，之前觉得总是转不过来弯，今天试着详细的梳理一下，将这个地方搞透。
参照：https://chenqx.github.io/2014/09/29/Algorithm-Recursive-Programming/
1. 概念
递归算法，其实质是将问题分解成规模缩小的同类问题的子问题，然后递归的调用自身来解决问题。
递归算法的特点有：
- 在方法里面调用自身
- 在使用递归策略的时候，必须有一个明确的递归结束条件，称为递归出口
- 递归算法解决问题的效率较低，而且在调用的过程之中，每一层的返回点，局部变量等等都开辟了栈来存储，如果其递归的过程比较多，那么容易造成栈溢出问题，所以一般要小心使用递归算法来解决问题。
递归算法的要求有：
- 每次调用在规模上面都有所缩小，通常是减半
- 相邻两次重复之间有紧密联系。通常前一次的输出就是后一次的输入
- 在问题的规模极小，可以作为退出条件时直接给出解答，而不再做递归调用。
2. 以计算阶乘为例演示递归算法的使用
由于阶乘具有：对某个数的阶乘=这个数*比其小一个数的阶乘，所以一开始我们可以这样编写程序：
Integer factorial(Integer n){
return factorial(n-1)*n;
}
但是这种表示方式，有一点是缺失的：没法退出。那么程序会跑到天荒地老。按照之前我们提到的，应该在规模足够小的时候直接退出，所以最后应该是这样的：
Integer factorial(Integer n) {
if (n == 1) {
return 1;
} else {
return factorial(n - 1);
}
}
此处我忽略了一些与递归无关的因素，比如范围的校验等等。但是可以看出递归算法的实质并不难：一个退出条件，一个分解问题。
之前的博文之中有提到二叉树的遍历，树是一种天然的适合递归算法的结构：每一个节点下面都是一棵规模更小的树，可以做到天然的分解问题。
3. 递归程序的基本步骤
- 初始化算法：向函数传递其启动所需的参数
- 检查是否符合返回条件。满足直接返回
- 使用更小的子问题界定答案
- 对子问题进行计算
- 将结果，通常是返回值，合并进入答案的表达式
- 返回结果
4. 使用归纳定义
有的时候，使用归纳程序很难获得子问题，但是使用归纳定义的(indectively defined) 数据集，可以使得子问题的获得更简单。归纳定义的数据集是根据自身定义的数据结构——这就叫做归纳定义(inductive defination)。
比如链表，链表之中的一个结构体是两部分组成的：其所持有的数据，还有指向另一个节点对象（或者是NULL，结束链表）的指针。因为节点结构体的内部包含一个指向节点结构体的指针，所以称为是归纳定义的。
使用归纳数据编写递归过程和递归程序非常类似，链表的定义也包含一个基线条件，与我们刚才讲的退出条件类似：此处是NULL指针。因为NULL指针会结束一个链表，所以我们也可以使用NULL指针作为基于链表的递归程序的结束条件。
5. 使用链表求和作为归纳定义的使用示例
假设我们有一个数字链表，并且想要求其中所有数字的和。那么有下面的步骤：
- 初始化算法：将要处理的第一个节点作为初始值，作为参数传递给函数
- 检查退出条件：程序需要确认检查当前节点是否为NULL，如果是的话就退出链表
- 将问题分解为更小的问题：变成当前节点的值加上除去此节点之后的链表求和。
此处连带Node定义的代码如下：
class Node {
Integer value;
Node next;
}
Integer sumAllLinkedList(Node start) {
if (start == null) {
return 0;
}
return start.value + sumAllLinkedList(start.next);
}
