什么是递归，一幅图表示：
递归是穷举的一种方式。本篇文章并不涉及递归定义的讲解，只是本人对递归的一点小理解。
结论：部分递归可以归纳成一个N叉树状的逻辑结构
比如这个题目：
x个苹果，一天只能吃一个、两个、或者三个，问多少天可以吃完
拿到这问题第一时间知道这肯定要用递归来解决，但是总觉着无处下手。
这个时候我们不妨找一个我们最熟悉的案例来过一下递归的结构，那我们掏出BinaryTree的DFS
public void visitNode(TreeNode node, Bean bean) {
if (node == null) {
return;
}
bean.num++;
visitNode(node.left, bean);
visitNode(node.right, bean);
}
发现其实思想是类似的，一个是递归左右子树，一个是递归三种情况。那是不是说这个题目也可以同样的用二叉树或者N叉树的结构表现出来呢？
那大致就长这个样子，我们要做的就是用DFS遍历这棵三叉树。
- 节点表示的是每天吃了一个两个还是三个苹果，
- 树的高度表示我们花了多少次循环完成找到的结果。
- 叶子节点表明递归条件终止
其实我们自己去想的时候也是这样子，列出所有的集合，然后找到符合条件的情况。只不过树状结构比较直观，列出了所有的情况。
代码如下所示：
public class XApple {
public void test() {
eatApple(3, 0, "");
}
private void eatApple(int x, int day, String result) {
eatAppleEveryDay(x, 1, day, result);
eatAppleEveryDay(x, 2, day, result);
eatAppleEveryDay(x, 3, day, result);
}
/**
* @param left 还剩苹果个数
* @param everyDay 每天吃的个数
* @param day 无意义，打印用，第几天
* @param result 无意义，打印用，结果传递
*/
private void eatAppleEveryDay(int left, int everyDay, int day, String result) {
result = result + "第" + day + "天吃" + everyDay + "个|";
left -= everyDay;
if (left < 0) {
return;
}
if (left == 0) {
System.out.print(result + "\n");
return;
}
eatApple(left, ++day, result);
}
}
虽然有的递归可以抽象成N叉树的方式来加深理解，比如全排列，N皇后，汉诺塔等经典递归问题（这里又涉及到回溯）。
但是有一些需要用递归的就无法抽象成N叉树的样子，比如斐波那契数列，阶乘等就不好抽象，所以还是有局限性。
我们直观上看这几个方法是顺序执行的：
eatAppleEveryDay(x, 1, day, result);
eatAppleEveryDay(x, 2, day, result);
eatAppleEveryDay(x, 3, day, result);
就有时候总会有一种错觉，就是这几个方法会按照123的顺序来顺序执行，吃一个总是在最前面，那岂不是每次都需要先吃一个苹果才会走后面的2跟3。
那我们再简化一下，4个苹果，每天吃一个或者两个，我们去掉打印需要，那代码如下所示。
public void test() {
eat(4, 0);
}
private void eat(int x, int day) {
eatPerDay(x, 1, day);
eatPerDay(x, 2, day);
}
private void eatPerDay(int left, int everyDay, int day) {
left -= everyDay;
if (left <= 0) {
return;
}
eat(left, ++day);
}
我们自己来想，总会有一个答案是第一天吃两个，第二天吃两个。也就是执行了两次eatPerDay(x, 2, day);, 嗯？这个2-2是怎么来的呢？
为什么没有执行吃一个的代码也就是eatPerDay(x, 1, day);？怎么可能不执行？
不执行第一句是怎么执行到第二句的？
最浅显容易理解的答案是1-1-1-1，也就是4天每天吃1个。这个打到条件return之后会执行1-1-1-2，当然这个是不满足条件的，那这个是怎么执行过去的呢？越来越迷糊，感觉对程序运行产生了怀疑。
再退一步，如果我们什么都不干预，只需要执行4层，是会产生2^4=16中答案的，我们从中挑出我们想要的摒弃掉不想要的，树状结构就是这么来的，树状结构只是结构，并不代表执行的次数只会执行一次。
如果我们把需要执行4层的所有的结果都不加控制的输出也就是从左往右深度遍历二叉树：
1-1-1-1
1-1-1-2
1-1-2-1
...
2-2-1-1
...
2-2-2-2
一共16条结果，这其中2-2-1-1其实是我们需要的结果，只不过我们只需要它的主干，后面的1-1不需要所以直接就不往后执行了，并不是2-2凭空开始执行的。
这里写一下加深理解，自己每次看到这个XApple也会懵一阵子，好记性不如烂笔头，写下来好了。
网友评论