三道题套路解决递归问题
    fucking-algorithm-递归详解

    递归解题三部曲：

    1. 找整个递归的终止条件：递归应该在什么时候结束？
    2. 找返回值：应该给上一级返回什么信息？
    3. 本级递归应该做什么：在这一级递归中，应该完成什么任务？

    **
    我们的重心应该放在关注这三点上，而不是去纠结这一层函数做了什么，它调用自身后的下一层函数又做了什么，即不要去纠结每一级调用和返回的细节

    递归解释的阅读笔记 - 图1

    递归是一种编程技巧，一种解决问题的思维方式；分治算法和动态规划很大程度上是递归思想基础上的

    分治算法将在这节讲解，以最经典的归并排序为例，它把待排序数组不断二分为规模更小的子问题处理，这就是 “分而治之” 这个词的由来。显然，排序问题分解出的子问题是不重复的，如果有的问题分解后的子问题有重复的（重叠子问题性质），那么就交给动态规划算法去解决！


    递归训练的是什么？

    • 训练逆向思考的能力。递推的思维是正常人的思维，总是看着眼前的问题思考对策，解决问题是将来时(迭代)；递归的思维（反向），逼迫我们倒着思考，看到问题的尽头，把解决问题的过程看做过去时。
    • 练习分析问题的结构，把问题分解成相同结构的小问题时，你能敏锐发现这个特点，进而高效解决问题。
    • 跳出细节，从整体上看问题。相对于着重于细节的迭代解法，递归代码清爽优雅(参考二叉树的遍历、归并排序）
    1. void sort(Comparable[] a){    
    2.     int N = a.length;
    3.     // 这么复杂，是对排序的不尊重。我拒绝研究这样的代码。
    4.     for (int sz = 1; sz < N; sz = sz + sz)
    5.         for (int lo = 0; lo < N - sz; lo += sz + sz)
    6.             merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
    7. }
    9. /* 我还是选择递归，简单，漂亮 */
    10. void sort(Comparable[] a, int lo, int hi) {
    11.     if (lo >= hi) return;
    12.     int mid = lo + (hi - lo) / 2;
    13.     sort(a, lo, mid); // 排序左半边
    14.     sort(a, mid + 1, hi); // 排序右半边
    15.     merge(a, lo, mid, hi); // 合并两边
    16. }

    **