递归，不是递给你一只乌龟，他是一种算法。递归就是在运行的过程中调用自己，他是把一个大的问题转化为一个与原问题相似的规模较小的问题来解决。
先讲个故事吧。
从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？“从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？‘从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？……’”
这个故事严格来说并不是递归，因为递归必须满足两个条件：
- 一个是调用自己，并且要比原问题的规模小。
- 一个是必须要有终止条件，否则会形成死循环。
这个故事虽然也在调用自己，但问题的规模并没有变小，并且它也没有终止条件，所以他不能算是递归。调用自己必须要与原问题做同样的事并且规模要小，当规模小到一定条件的时候就不需要在调用自己，直接返回。还一个要有终止条件，如果递归没有终止条件，将会无休止的继续下去，直到出现 StackOverflowError ，并且终止条件必须要在调用自己之前。
private void test(int count) {
// 终止条件必须在调用自己之前。
if (count < 0)
return;
System.out.println(count--);
test(count);
}
如果终止条件放到调用自己之后，就会出现死循环。
private void test(int count) {
System.out.println(count--);
test(count);
// 终止条件放在调用自己之后（错误代码，要避免出现）。
if (count < 0)
return;
}
递归的理解
递归分为两部分，一部分是递，一部分是归，递就是往下传递，归就是往回走 ，无论走到什么地方，最终都会回到函数调用处，也就是说递归无论走多远最终都会回来的。在递归中如果最多只调用自己一次，可以把它看做是对链表的遍历，如下图所示。
他是先往后走，当走到链表末尾的时候在往回走，每个节点都可以访问两遍，所以打印链表的时候可以在往后走的时候打印，也可以在往回走的时候打印。如果往后走的时候打印就是链表的正序打印，如果往回走的时候打印就是链表的逆序打印。
链表的正序打印
public void printLinkedList(ListNode listNode) {
if (listNode == null)
return;
// 先访问节点的值，再递归。
System.out.println(listNode.val);
printLinkedList(listNode.next);
}
链表的逆序打印
public void reversLinkedList(ListNode listNode) {
if (listNode == null)
return;
// 先递归再访问节点。
reversLinkedList(listNode.next);
System.out.println(listNode.val);
}
其实我们还可以这样理解，递归往后走的时候就是把当前的状态不停的压栈，往回走的时候就是出栈，如果压栈的时候打印节点就是正序，如果出栈的时候打印节点就是逆序。来看一下阶乘的递归解法。
public int f(int num) {
if (num == 1)
return 1;
return num * f(num - 1);
}
假设当 num 等于 5 的时候递归过程，如下图所示，当规模足够小的时候就不需要调用自己了，直接返回。
如果递归调用自己两次，可以把它看做二叉树的 DFS 遍历，这个估计大家能明白。如果递归调用自己 n 次，可以把它看做 n 叉树的 DFS 遍历。如果递归中有一些判断条件不需要调用自己，可以把它看做剪枝，理清了这点对于理解递归很有帮助。如下图，是一棵 n 叉树的 DFS 遍历，通过它我们可以看到递归执行的过程。其中递就是往下传递，归就是往回走。
只要搞懂了它的执行顺序，理解递归就简单了，我们来看这样一道题，求 n 叉树的最大深度，只需要通过递归的方式计算当前节点所有子树的最大深度加上 1 即可。
public int maxDepth(Node root) {
if (root == null)
return 0;
int max = 0;// 所有子树的最大深度。
for (Node node : root.children) // 遍历所有子节点。
max = Math.max(max, maxDepth(node));// 递归计算子树的最大深度，保存最大值。
return max + 1;
}
再来看打印当前目录下的所有文件的递归写法，如果是文件直接打印，如果是目录就递归调用。
// 打印当前目录下的所有文件。
private void printFile(File dir) {
File[] files = dir.listFiles();// 获取子节点。
for (File file : files) { // 遍历所有子节点。
if (file.isFile()) {// 如果是文件直接打印。
System.out.println("文件名:" + file.getName());
} else {
printFile(file);// 如果是目录就递归。
}
}
}
给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
我们画个图看下，因为不能有重复的组合，所以选择当前数字的时候就不能再选择前面的数字，否则会出现 [3,5] 和 [5,3] 两种组合。我们可以把它看做是一棵 n 叉树，其中 n 是数组的长度。
对这棵树进行 DFS 遍历，大致轮廓可以写出来。
// 递归函数。
private void dfs(List<Integer> path, int sums[], int target) {
if (终止条件) { // 终止条件必须要有。
return;
}
for (int i = 0; i < sums.length; i++) {// 递归所有子树。
dfs(path, sums, "新的target");
}
}
这里的终止条件是什么呢，就是 target 等于 0 的时候，递归就不在往下走。
if (target==0) { // 终止条件必须要有。
return;
}
往下递归的时候如果当前值比 target 大，就不要选了，如果不比 target 大，就把他加入到 path 中，表示选了他，选择之后在递归调用的时候 target 值就要减去选择的值。
// 如果当前值大于 target 就不要选了。
if (target < sums[i])
continue;
path.add(sums[i]); // 否则就把他加入到集合中。
dfs(path, sums, target - sums[i]);
我们来看下完整代码。
// 递归函数
private void dfs(List<Integer> path, int sums[], int target, int index) {
if (target == 0) {//终止条件必须要有
System.out.println(Arrays.toString(path.toArray()));
return;
}
// 因为选择当前数字的时候为了防止出现重复结果，不能选择他前面的，所以这里的 i 是从 index 开始的。
for (int i = index; i < sums.length; i++) {// 递归所有子树。
// 如果当前值大于 target 就不要选了。
if (sums[i] > target)
continue;
path.add(sums[i]); // 否则就把他加入到集合中。
dfs(path, sums, target - sums[i], i);// 递归下一层。
path.remove(path.size() - 1);// 这里是回溯，往回走的时候移除（在回溯算法章节中再讲）。
}
}
