博客

最近参与了一个比较大的项目，其中用到的各种聚合算法理解起来也比较困难，尤其用到了递归的地方。

递归是算法中一种非常重要的思想，应用也很广，小到阶乘,再在工作中用到的比如统计文件夹大小，大到 Google 的 PageRank 算法都能看到

最近看了不少递归的文章，收获不小，不过我发现大部分网上的讲递归的文章都不太全面，主要的问题在于解题后大部分都没有给出相应的时间/空间复杂度，而时间/空间复杂度是算法的重要考量!递归算法的时间复杂度普遍比较难（需要用到归纳法等），换句话说，如果能解决递归的算法复杂度，其他算法的时间复杂度也基本不在话下。另外，递归算法的时间复杂度不少是不能接受的，如果发现算出的时间复杂度过大，则需要转换思路，看下是否有更好的解法 ，这才是根本目的，不要为了递归而递归！

什么是递归

简单地说，就是如果在函数中存在着调用函数本身的情况，这种现象就叫递归。

以阶乘函数为例,如下, 在 factorial 函数中存在着 factorial(n – 1) 的调用，所以此函数是递归函数

public int factorial(int n) {
    if (n < =1) {
        return1;
    }
    return n * factorial(n - 1)
}

进一步剖析「递归」，先有「递」再有「归」，「递」的意思是将问题拆解成子问题来解决， 子问题再拆解成子子问题，…，直到被拆解的子问题无需再拆分成更细的子问题（即可以求解），「归」是说最小的子问题解决了，那么它的上一层子问题也就解决了，上一层的子问题解决了，上上层子问题自然也就解决了,…,直到最开始的问题解决,文字说可能有点抽象，那我们就以阶层 f(6) 为例来看下它的「递」和「归」。



求解问题 f(6), 由于 f(6) = n * f(5), 所以 f(6) 需要拆解成 f(5) 子问题进行求解，同理 f(5) = n * f(4) ,也需要进一步拆分,… ,直到 f(1), 这是「递」，f(1) 解决了，由于 f(2) = 2 f(1) = 2 也解决了,… f(n)到最后也解决了，这是「归」，所以递归的本质是能把问题拆分成具有相同解决思路的子问题，。。。直到最后被拆解的子问题再也不能拆分，解决了最小粒度可求解的子问题后，在「归」的过程中自然顺其自然地解决了最开始的问题。

递归算法通用解决思路

1. 一个问题可以分解成具有相同解决思路的子问题，子子问题，换句话说这些问题都能调用同一个函数
2. 经过层层分解的子问题最后一定是有一个不能再分解的固定值的（即终止条件）,如果没有的话,就无穷无尽地分解子问题了，问题显然是无解的。

递归解题的基本套路

1. 明确函数的功能
2. 寻找问题与子问题间的关系
3. 用代码表示出关系
4. 推导时间复杂度,如果发现递归时间复杂度不可接受，则需转换思路对其进行改造

下面来举个very简单的例子

输入一个正整数n，输出n!的值。其中n!=123*…*n,即求阶乘

1.定义这个函数，明确这个函数的功能

/**
 * 求 n 的阶乘
 */
public int factorial(int n) {
}

2.寻找问题与子问题的关系

我们以 f(n) 来表示 n 的阶乘， 显然 f(n) = n * f(n – 1), 同时临界条件是 f(1) = 1

3.将第二步的递推公式用代码表示出来补充到步骤 1 定义的函数中

/**
 * 求 n 的阶乘
 */
public int factorial(int n) {
    // 第二步的临界条件
    if (n < =1) {
        return 1;
    }

    // 第二步的递推公式
    return n * factorial(n-1)
}

4.求时间复杂度

由于 f(n) = n * f(n-1) = n * (n-1) * … * f(1),总共作了 n 次乘法，所以时间复杂度为 n。