一文搞懂递归、备忘录、动态规划

Delina

原文链接：一文搞懂递归、备忘录、动态规划

• 递归
  
  
  

递归算法是一类非常常用的算法，它是一种直接或间接调用原算法本身的算法。递归算法最大的特点就是“自己调用自己”，对于一些具有递归特性的问题，使用递归算法来解决会更加简单明了，且易于实现。
在使用递归算法解决实际的问题时，要自顶向下地将一个大问题拆分成同类的小问题，然后利用同类问题这一特性构造出解决问题的递归函数，也就是这种“自己调用自己”的模型，再通过程序实现这个递归函数。

​

下面通过一个实例理解递归算法。
走楼梯问题：一个楼梯共有10级台阶，一个人从下往上走，他可以一次走一个台阶，也可以一次走两个台阶。请问这个人有多少种走法走完这10级台阶？
这是一道经典而有趣的算法题，本题有很多种解法，其中最为经典而简洁的解法是使用递归算法解决。我们先来看一下如何使用递归法求解此题。
因为这个人一次可以走一个台阶，也可以走两个台阶，所以他可以有很多种组合方法走完这10级台阶。例如可以如图（1）所示这样上楼：
走法一：1--> 1-->1--> 1-->1--> 1-->1--> 1-->1--> 1，如图（1）所示：

​

也就是每步都走一个台阶。
也可以如图（2）所示这样上楼：
走法二：2-->1--> 1-->1--> 1-->1--> 1-->1--> 1，如图（2）所示。

​
也就是先上两级台阶，再一步一个台阶地上8个台阶。
这样看来，这个人可以有很多种方式走完这10个台阶，那么我们要如何计算共有多少种走法呢？
试想如果这个人要走到第10级台阶，必然存在且仅存在以下两种情形：
（1）此人先登到第8级台阶上，然后在第8级台阶处向上直接登2个台阶，而不经过第9级台阶，如图（3）所示；

​

（2）此人登上了第9级台阶，再向上登1级台阶即可到顶，如图（4）所示。


​

有的读者可能会有这样的质疑：“此人在第8级台阶处向上登1级台阶到第9级台阶上，然后再向上登1级台阶到第10级台阶，这也是一种情形啊?”其实这种场景已经包含在第2种情形之中了，第1种情形与第2种情形是以是否登到第9级台阶上作为划分的，只要登到第9级台阶之上就都属于第2种情形。
因为这个人一次只能走一个台阶或者两个台阶，所以此人要登到第10级台阶上只可能存在上述两种可能，所以这种划分是完备的。
假设这个人登到第8级台阶（第1种情形）的走法有x种，登到第9级台阶（第2种情形）的走法有y种，很显然，此人登上10级台阶的走法共有x+y种。
我们用F(10)表示这个人登上10级台阶总共的走法，用F(9)表示他登上9级台阶总共的走法，用F(8)表示他登上8级台阶总共的走法，则有F(10)=F(9)+F(8)。不难想象，类比F(10)的计算，我们可以得到F(9)的计算公式：F(9)=F(8)+F(7)以及F(8)的计算公式：F(8)=F(7)+F(6)，……，依此类推。当只有1级台阶时其走法只有1种，所以F(1)=1；当只有2级台阶时其走法只有2种，所以F(2)=2。所以我们可以总结出计算F(n)的公式：

​

不难看出这是一个递归公式，所以可以使用递归算法求解此题。求解此题的Java代码实现如下：
public class ClimbStairs {
    private static int getClimbWays(int n) {
        if (n == 1) {
            return 1;
        } else if (n == 2) {
            return 2;
        } else {
            return getClimbWays(n-1) + getClimbWays(n-2);
        }
    }
     public static void main(String []args) {
        int climbWays = 0;
        climbWays = getClimbWays(10);
        System.out.println("There are "+ climbWays + " ways to climb 10 steps ");
    }
}

代码中函数getClimbWays()是一个递归函数，它的作用是返回登上n级台阶总共的走法数。在函数getClimbWays()内部会判断n的值，当进行到某一层递归调用中n的值变为1或者2时，该函数即可返回1或2，此为该递归调用的出口。如果n的值不等于1或2，则递归地调用getClimbWays()函数，返回getClimbWays(n-1) + getClimbWays(n-2)的值即为本题的答案。上述代码的执行结果如图（5）所示。

​
如图（5）所示，登上10级台阶共有89种走法。
深入思考上面这个递归算法不难发现，该算法其实存在着很多冗余的计算。因为我们在计算F(n)时首先要计算F(n-1)和F(n-2)，而计算F(n-1)时又要先计算F(n-2)和F(n-3)，这样F(n-2)就计算了两遍。对应到上面的代码，就是函数getClimbWays()会执行很多次重复冗余的调用，我们可以通过图（6）直观地看到这一点。

​

如图（6）所示，深蓝色框中的函数只需要调用一次即可，而在这棵递归树中每一个方框中的函数都会被调用到，所以使用递归算法解决本题会存在这大量的冗余计算。
这也就是递归算法的一大缺点——重复冗余的计算。如果递归函数中存在多次递归调用的情形（例如这里的F(n-1)+F(n-2)），则势必存在这种重复计算的情况。这也是导致递归算法性能不高的一个重要原因。

• 备忘录
  
  

如何解决重复计算的问题呢？直观的想法是，我们可以将计算得到的中间结果保存在一个叫做“备忘录”的结构中，这样再次执行相同的计算过程时，就没有必要真的计算了，而是直接从“备忘录”中取出记录下来的结果，这样的性能会比单纯地使用递归调用高很多。

​

下面给出备忘录方法的代码实现。

public class ClimbStairs {
    private static HashMap<Integer,Integer> memorandum
    = new HashMap<Integer,Integer>();
    private static int count = 0;

    private static int getClimbWays(int n) {
        count++;
        if (n == 1) {
            return 1;
        } else if (n == 2) {
            return 2;
        } else {
            Integer rec1 = memorandum.get(n-1);
            Integer rec2 = memorandum.get(n-2);
            if (rec1 == null) {
                rec1= getClimbWays(n-1);
                memorandum.put(n-1,rec1);
            }
            if (rec2 == null) {
                rec2 =  getClimbWays(n-2);
                memorandum.put(n-2,rec2);
            }
            return rec1+rec2;
        }
    }
     public static void main(String []args) {
        int climbWays = 0;
        climbWays = getClimbWays(10);
        System.out.println("count = " + count);
        System.out.println("There are "+ climbWays +
                                  " ways to climb 10 steps ");
    }
}

在上述代码中，在类ClimbStairs 中定义了一个HashMap类型的成员memorandum，这就是所谓的备忘录。在函数getClimbWays(int n)中，如果参数n>2，则先尝试从memorandum中获取key为n-1和n-2的value，也就是getClimbWays(n-1)和getClimbWays(n-2)的值，这样就省去了每次都要递归调用函数getClimbWays()的消耗。如果获取的值为null，则说明还没有还没有执行getClimbWays()函数，因此需要执行一次getClimbWays()函数，并将返回的结果以键值对<key,value>的形式保存到memorandum中，以便下一次使用时可直接从备忘录中获取。
另外，为了计算备忘录方法可以减少多少次递归函数getClimbWays()的调用，我们定义了一个计数器变量count，并在进入函数getClimbWays()时将count自动加1，以便统计调用的次数。实验证明，调用计算10级台阶的走法getClimbWays(10)，使用单纯的递归方法，需调用函数getClimbWays()共109次，而使用备忘录方法则仅需调用函数getClimbWays()共17次！

• 动态规划
  
  

那么有没有一种更为高效的算法来解决这个问题呢？无论是递归算法还是备忘录算法，其本质都是一种自顶向下的运算方式，也就是从F(10)开始逐级分解该问（F(9),F(8),F(7)……），重复调用自身过程的同时问题的规模不断缩小。其实我们还可以自底向上的运算，也就是从F(1)=1，F(2)=2计算出F(3)=3，再从F(2)=2，F(3)=3计算出F(4)=5，……以此类推，一直求到F(n)。由于采用这种方式可将每一步的计算结果都记录下来，所以在这个过程中没有任何冗余的运算，算法的效率会高很多。同时运算的过程中没有任何递归调用，在一定程度上也消除了因递归调用而带来的系统开销。我们称这种利用问题本身的递归特性，自底向上逐级迭代计算出最优解的方法为动态规划算法。
走楼梯问题动态规划算法的Java代码实现如下。

public class ClimbStairs {
     private static int getClimbWays(int n) {

        int a = 1;
        int b = 2;
        int tmp = 0;
        int i = 0;
        if (n == 1) {
            return 1;
        } else if (n == 2) {
            return 2;
        } else {
            for (i=3; i<=n; i++) {
                tmp = a + b;
                a = b;
                b = tmp;
            }
            return tmp;
    }
}

     public static void main (String[] args) {
        int climbWays = 0;
        climbWays = getClimbWays(10);
        System.out.println("There are "+ climbWays + " ways to climb 10 steps ");

    }
}

上述代码中函数getClimbWays()的作用是返回登上n级台阶总共的走法数。当n等于1时表示只有一个台阶，此时只有一种走法，所以函数返回1；当n等于2时表示只有2个台阶，此时只有两种走法，所以函数返回2；否则需要通过一个循环来计算共有多少种走法。该循环就是上面所讲的自底向上的求解过程，即通过初始值a=1（F(1)的值）和b=2（F(2)的值）来计算F(3)，进而计算F(4)，F(5)，……，直到计算出F(n)，并将其返回。上述代码的执行结果如图（7）所示。

​

显然，使用动态规划算法计算的结果与使用递归算法计算的结果是相同的。

• 总结
  
  
  

通过上面这个实例，相信大家对动态规划算法能有一个比较直观的理解。动态规划算法与递归算法的相似之处在于动态规划算法也是将一个规模较大的问题分解为规模较小的问题，然后逐一求解再汇聚成一个大的问题，但不同之处是动态规划算法是以自底向上的方式计算最优解，而递归法和备忘录法则都采用自顶向下的方式，备忘录法只是在递归法的基础上增加了“备忘录”数据结构，从而减少了冗余的递归调用。因此动态规划算法可以在计算过程中保存已解决的子问题答案，每个子问题只计算一次，这样可以减少冗余的计算，提高解决问题的效率。
在使用动态规划算法解决问题时要把握两个基本要素，它们分别是：

• 具备最优子结构
  
• 具备子问题重叠性质
  
  

只有当一个问题具备了这两个基本要素才能使用动态规划算法来求解。
设计动态规划算法的第一步通常是要刻画出问题的最优子结构。当一个问题的最优解包含了其子问题的最优解时，就称该问题具有最优子结构性质。以走楼梯问题为例，我们首先可以归纳出该问题的递归公式，即F(n)=F(n-1)+F(n-2),n>2，那么F(n-1)和F(n-2)就是F(n)的最优子结构，因为F(n-1)和F(n-2)是F(n)子问题的最优解。
另外使用动态规划算法求解的问题还应具备子问题的重叠性质。以上面这个走楼梯问题为例，在递归算法中每次产生的子问题并不一定总是新问题，很多子问题都需要被反复的计算多次，就像图（6）中所示的那些方框中的函数调用。而动态规范算法正是利用了这种子问题重叠的性质，采用自底向上的方式计算，每个子问题只计算一次，然后将结果保存到变量（例如上述代码中的变量a，b，tmp）中或者表格中（可以使用数组等数据结构来存储），当再次使用时只需要查询并读取即可，这样可以提高解题的效率。
“爬楼梯”问题是一道非常简单的既可用递归法，也可用动态规划算法求解的问题。之所以用这样一个简单的问题来解释递归、备忘录和动态规划，目的就是为了让大家更多地关注递归、备忘录和动态规划的本质，从而更加轻松地理解这些算法的内涵和使用场景。在后续的文章中，我会讲解一些更为复杂的问题。但是万变不离其宗，只要掌握了递归、备忘录和动态规划的本质和它们之间的区别，很多看似复杂的问题其实也都不难解决