乐趣区

关于算法:递-归-详-解

jiezi

———–

首先阐明一个问题，简略论述一下递归，分治算法，动静布局，贪婪算法这几个货色的区别和分割，心里有个印象就好。

递归是一种编程技巧，一种解决问题的思维形式；分治算法和动静布局很大水平上是递归思维根底上的（尽管动静布局的最终版本大都不是递归了，但解题思维还是离不开递归），解决更具体问题的两类算法思维；贪婪算法是动静布局算法的一个子集，能够更高效解决一部分更非凡的问题。

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

递归详解

介绍分治之前，首先要弄清楚递归这个概念。

递归的根本思维是某个函数间接或者间接地调用本身，这样就把原问题的求解转换为许多性质雷同然而规模更小的子问题。咱们只须要关注如何把原问题划分成符合条件的子问题，而不须要去钻研这个子问题是如何被解决的。递归和枚举的区别在于：枚举是横向地把问题划分，而后顺次求解子问题，而递归是把问题逐级分解，是纵向的拆分。

以下会举例说明我对递归的一点了解，如果你不想看上来了，请记住这几个问题怎么答复：

  1. 如何给一堆数字排序？答：分成两半，先排左半边再排右半边，最初合并就行了，至于怎么排右边和左边，请从新浏览这句话。
  2. 孙悟空身上有多少根毛？答：一根毛加剩下的毛。
  3. 你往年几岁？答：去年的岁数加一岁,1999 年我出世。

递归代码最重要的两个特色：完结条件和自我调用。自我调用是在解决子问题，而完结条件定义了最简子问题的答案。

int func(你往年几岁) {
    // 最简子问题，完结条件
    if (你 1999 年几岁) return 我 0 岁;
    // 自我调用，放大规模
    return func(你去年几岁) + 1;   
}

其实认真想想，递归使用最胜利的是什么？我认为是数学归纳法。咱们高中都学过数学归纳法，应用场景大略是：咱们推不进去某个求和公式，然而咱们试了几个比拟小的数，仿佛发现了一点法则，而后编了一个公式，看起来应该是正确答案。然而数学是很谨严的，你哪怕穷举了一万个数都是正确的，然而第一万零一个数正确吗？这就要数学归纳法施展神威了，能够假如咱们编的这个公式在第 k 个数时成立，如果证实在第 k + 1 时也成立，那么咱们编的这个公式就是正确的。

那么数学归纳法和递归有什么分割？咱们方才说了，递归代码必须要有完结条件，如果没有的话就会进入无穷无尽的自我调用，直到内存耗尽。而数学证实的难度在于，你能够尝试有穷种状况，然而难以将你的论断延长到无穷大。这里就能够看出分割了 —— 无穷。

递归代码的精华在于调用本人去解决规模更小的子问题，直到达到完结条件；而数学归纳法之所以有用，就在于一直把咱们的猜想向上加一，扩充论断的规模，没有完结条件，从而把论断延长到无穷无尽，也就实现了猜想正确性的证实。

为什么要写递归

首先为了训练逆向思考的能力。递推的思维是正常人的思维，总是看着眼前的问题思考对策，解决问题是未来时；递归的思维，逼迫咱们倒着思考，看到问题的止境，把解决问题的过程看做过来时。

第二，练习剖析问题的构造，当问题能够被分解成雷同构造的小问题时，你能敏锐发现这个特点，进而高效解决问题。

第三，跳出细节，从整体上看问题。再说说归并排序，其实能够不必递归来划分左右区域的，然而代价就是代码极其难以了解，大略看一下代码（归并排序在前面讲，这里大抵看懂意思就行，领会递归的妙处）：

void sort(Comparable[] a){    
    int N = a.length;
    // 这么简单，是对排序的不尊重。我回绝钻研这样的代码。for (int sz = 1; sz < N; sz = sz + sz)
        for (int lo = 0; lo < N - sz; lo += sz + sz)
            merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
}

/* 我还是抉择递归，简略，丑陋 */
void sort(Comparable[] a, int lo, int hi) {if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    sort(a, lo, mid); // 排序左半边
    sort(a, mid + 1, hi); // 排序右半边
    merge(a, lo, mid, hi); // 合并两边
}

看起来简洁丑陋是一方面，要害是 可解释性很强：把左半边排序，把右半边排序，最初合并两边。而非递归版本看起来不知所云，充斥着各种难以了解的边界计算细节，特地容易出 bug 且难以调试，人生苦短，我更偏向于递归版本。

显然有时候递归解决是高效的，比方归并排序，有时候是低效的，比方数孙悟空身上的毛，因为堆栈会耗费额定空间，而简略的递推不会耗费空间。比方这个例子，给一个链表头，计算它的长度：

/* 典型的递推遍历框架，须要额定空间 O(1) */
public int size(Node head) {
    int size = 0;
    for (Node p = head; p != null; p = p.next) size++;
    return size;
}
/* 我偏要递归，万物皆递归，须要额定空间 O(N) */
public int size(Node head) {if (head == null) return 0;
    return size(head.next) + 1;
}

写递归的技巧

我的一点心得是：明确一个函数的作用并置信它能实现这个工作，千万不要试图跳进细节。千万不要跳进这个函数外面希图探索更多细节，否则就会陷入无穷的细节无法自拔，人脑能压几个栈啊。

先举个最简略的例子：遍历二叉树。

void traverse(TreeNode* root) {if (root == nullptr) return;
    traverse(root->left);
    traverse(root->right);
}

这几行代码就足以涤荡任何一棵二叉树了。我想说的是，对于递归函数traverse(root)，咱们只有置信：给它一个根节点root，它就能遍历这棵树，因为写这个函数不就是为了这个目标吗？所以咱们只须要把这个节点的左右节点再甩给这个函数就行了，因为我置信它能实现工作的。那么遍历一棵 N 叉数呢？太简略了好吧，和二叉树截然不同啊。

void traverse(TreeNode* root) {if (root == nullptr) return;
    for (child : root->children)
        traverse(child);
}

至于遍历的什么前、中、后序，那都是不言而喻的，对于 N 叉树，显然没有中序遍历。

以下 详解 LeetCode 的一道题来阐明：给一课二叉树，和一个目标值，节点上的值有正有负，返回树中和等于目标值的门路条数，让你编写 pathSum 函数：

/* 来源于 LeetCode PathSum III：https://leetcode.com/problems/path-sum-iii/ */
root = [10,5,-3,3,2,null,11,3,-2,null,1],
sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11
/* 看不懂没关系，底下有更具体的剖析版本，这里突出体现递归的简洁柔美 */
int pathSum(TreeNode root, int sum) {if (root == null) return 0;
    return count(root, sum) + 
        pathSum(root.left, sum) + pathSum(root.right, sum);
}
int count(TreeNode node, int sum) {if (node == null) return 0;
    return (node.val == sum) + 
        count(node.left, sum - node.val) + count(node.right, sum - node.val);
}

题目看起来很简单吧，不过代码却极其简洁，这就是递归的魅力。我来简略总结这个问题的 解决过程：

首先明确，递归求解树的问题必然是要遍历整棵树的，所以 二叉树的遍历框架（别离对左右孩子递归调用函数自身）必然要呈现在主函数 pathSum 中。那么对于每个节点，他们应该干什么呢？他们应该看看，本人和脚底下的小弟们蕴含多少条符合条件的门路。好了，这道题就完结了。

依照后面说的技巧，依据方才的剖析来定义分明每个递归函数应该做的事：

PathSum 函数：给他一个节点和一个目标值，他返回以这个节点为根的树中，和为目标值的门路总数。

count 函数：给他一个节点和一个目标值，他返回以这个节点为根的树中，能凑出几个以该节点为门路结尾，和为目标值的门路总数。

/* 有了以上铺垫，具体正文一下代码 */
int pathSum(TreeNode root, int sum) {if (root == null) return 0;
    int pathImLeading = count(root, sum); // 本人为结尾的门路数
    int leftPathSum = pathSum(root.left, sum); // 右边门路总数（置信他能算进去）int rightPathSum = pathSum(root.right, sum); // 左边门路总数（置信他能算进去）return leftPathSum + rightPathSum + pathImLeading;
}
int count(TreeNode node, int sum) {if (node == null) return 0;
    // 我本人能不能独当一面，作为一条独自的门路呢？int isMe = (node.val == sum) ? 1 : 0;
    // 右边的小老弟，你那边能凑几个 sum - node.val 呀？int leftBrother = count(node.left, sum - node.val); 
    // 左边的小老弟，你那边能凑几个 sum - node.val 呀？int rightBrother = count(node.right, sum - node.val);
    return  isMe + leftBrother + rightBrother; // 我这能凑这么多个
}

还是那句话，明确每个函数能做的事，并置信他们可能实现。

总结下，PathSum 函数提供的二叉树遍历框架，在遍历中对每个节点调用 count 函数，看出先序遍历了吗（这道题什么序都是一样的）；count 函数也是一个二叉树遍历，用于寻找以该节点结尾的目标值门路。好好领会吧！

分治算法

归并排序，典型的分治算法；分治，典型的递归结构。

分治算法能够分三步走：合成 -> 解决 -> 合并

  1. 合成原问题为构造雷同的子问题。
  2. 合成到某个容易求解的边界之后，进行第归求解。
  3. 将子问题的解合并成原问题的解。

归并排序，咱们就叫这个函数 merge_sort 吧，依照咱们下面说的，要明确该函数的职责，即 对传入的一个数组排序。OK，那么这个问题能不能分解呢？当然能够！给一个数组排序，不就等于给该数组的两半别离排序，而后合并就完事了。

void merge_sort(一个数组) {if (能够很容易解决) return;
    merge_sort(左半个数组);
    merge_sort(右半个数组);
    merge(左半个数组, 右半个数组);
}

好了，这个算法也就这样了，齐全没有任何难度。记住之前说的，置信函数的能力，传给他半个数组，那么这半个数组就曾经被排好了。而且你会发现这不就是个二叉树遍历模板吗？为什么是后序遍历？因为咱们分治算法的套路是 合成 -> 解决（触底）-> 合并（回溯） 啊，先左右合成，再解决合并，回溯就是在退栈，就相当于后序遍历了。至于 merge 函数，参考两个有序链表的合并，几乎截然不同，上面间接贴代码吧。

上面参考《算法 4》的 Java 代码，很漂亮。由此可见，不仅算法思维思维重要，编码技巧也是挺重要的吧！多思考，多模拟。

public class Merge {
    // 不要在 merge 函数里结构新数组了，因为 merge 函数会被屡次调用，影响性能
    // 间接一次性结构一个足够大的数组，简洁，高效
    private static Comparable[] aux;

     public static void sort(Comparable[] a) {aux = new Comparable[a.length];
        sort(a, 0, a.length - 1);
    }

    private static void sort(Comparable[] a, int lo, int hi) {if (lo >= hi) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, lo, mid);
        sort(a, mid + 1, hi);
        merge(a, lo, mid, hi);
    }

    private static void merge(Comparable[] a, int lo, int mid, int hi) {
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++)
            aux[k] = a[k];
        for (int k = lo; k <= hi; k++) {if      (i > mid)              {a[k] = aux[j++]; }
            else if (j > hi)               {a[k] = aux[i++]; }
            else if (less(aux[j], aux[i])) {a[k] = aux[j++]; }
            else                           {a[k] = aux[i++]; }
        }
    }

    private static boolean less(Comparable v, Comparable w) {return v.compareTo(w) < 0;
    }
}

LeetCode 上有分治算法的专项练习，可复制到浏览器去做题：

https://leetcode.com/tag/divi…

退出移动版