关于递归的一点理解

什么是递归，一幅图表示：

递归是穷举的一种方式。本篇文章并不涉及递归定义的讲解，只是本人对递归的一点小理解。
结论：部分递归可以归纳成一个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遍历这棵三叉树。

1. 节点表示的是每天吃了一个两个还是三个苹果，
2. 树的高度表示我们花了多少次循环完成找到的结果。
3. 叶子节点表明递归条件终止

其实我们自己去想的时候也是这样子，列出所有的集合，然后找到符合条件的情况。只不过树状结构比较直观，列出了所有的情况。

代码如下所示：

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也会懵一阵子，好记性不如烂笔头，写下来好了。