《算法之美》-- 递归

"逐步生成结果”类问题之数值型

自下而上的递归(递推数学归纳,动态规划)

• 递归又叫递推，不仅仅是只是自上而下的，这样写只是利用了编程语言的便捷性
• 自上向下只是代码的现象，只是写成了这种形式，而本质是由小规模问题形成大规模问题，是自下而上的
• 在数学上是数学归纳法

为什么是数学归纳法？

• 解决简单情况下的问题，如斐波那契数列假设前两项之和是第三项
• 推广到复杂情况，这个过程叫做归纳
• 上面两步就是递归
• 如果递推的次数很明确，就用迭代（循环，减少方法开辟的栈空间）
• 如果有封闭形式，可以直接求解

例1：CC150—9_1走楼梯

/**
 有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶、3阶。
 请实现一个方法，计算小孩有多少种上楼的方式。
 为了防止溢出，请将结果Mod 1000000007

 给定一个正整数int n，请返回一个数，代表上楼的方式数。
 保证n小于等于100000。
 */
public class _9_1走楼梯 {
  static final int mod = 1000000007;

  public static void main(String[] args) {
    System.out.println(recursion2(7));
    System.out.println(recursion1(7));
    System.out.println(recursion3(7));
  }

  /**
   * n较小的时候就会超时
   * @param n
   * @return
   */
  public static long recursion1(int n) {
    if (n < 0) return 0;
    if (n == 0 || n == 1) return 1;
    if (n == 2) return 2;
    return recursion1(n - 1) % mod + recursion1(n - 2) % mod + recursion1(n - 3) % mod;
  }

  // 1 2 4 7 13 24 44
  public static int recursion2(int n) {
    if (n < 0) return 0;
    if (n == 0 || n == 1) return 1;
    if (n == 2) return 2;
    if (n == 3) return 4;
    int x1 = 1;
    int x2 = 2;
    int x3 = 4;
    for (int i = 4; i <= n; i++) {
      int x_1 = x1;
      x1 = x2 % mod;
      x2 = x3 % mod;
      x3 = ((x1 + x2) % mod + x_1) % mod;//注意此处
    }
    return x3;
  }

  public static int recursion3(int n) {
    long[][] base = {
        {0, 0, 1},
        {1, 0, 1},
        {0, 1, 1}};
    long[][] f1f2f3 = {{1, 2, 4}};
    return (int) Util.matrixMultiply(f1f2f3, Util.matrixPower(base, n - 1))[0][0];
  }
}

• 如果只有一个台阶，则只有一个解法
• 如果两个阶梯，走一步剩一个台阶，由于一个台阶只有一个解法，所以这走一步只有一个解法；走两步一个解法。所以两个台阶的是1 + 1 = 2种解法
• 如果三个阶梯，走一步剩两个台阶，由于两个个台阶只有两个个解法，所以这走两步步只有两个解法；走两步剩一个台阶，所以这走一步只有一个解法；走三步一个解法。所以三个台阶的是2 + 1 + 1 = 4种解法
• 依次迭代
• f(n) = f(n-1) + f(n-2) + f(n-3)

recursion2中(推荐用这种)

• x1,x2,x3其实代表着前三项，每次新算出一个数，不断的更新下个数的前三项
• 这是递归改循环

例2：CC150—9_2机器人走格子

**
 有一个X*Y的网格，一个机器人只能走格点且只能向右或向下走，要从左上角走到右下角。
 请设计一个算法，计算机器人有多少种走法。
 给定两个正整数int x,int y，请返回机器人的走法数目。保证x＋y小于等于12。
 */
public class _9_2机器人走格子 {
  public static void main(String[] args) {
    System.out.println(solve(6, 6));
    System.out.println(solve1(6, 6));
  }

  /**
   * 递归形式
   * @param x
   * @param y
   * @return
   */
  public static int solve(int x, int y) {

    if (x == 1 || y == 1) return 1;

    return solve(x - 1, y) + solve(x, y - 1);
  }

  /**
   * 迭代形式
   * @param m
   * @param n
   * @return
   */
  public static int solve1(int m, int n) {
    int[][] state = new int[m + 1][n + 1];
    for (int i = 1; i <= n; i++) {
      state[1][i] = 1;
    }
    for (int i = 1; i <= m; i++) {
      state[i][1] = 1;
    }
    for (int i = 2; i <= m; i++) {
      for (int j = 2; j <= n; j++) {
        state[i][j] = state[i][j - 1] + state[i - 1][j];
      }
    }
    return state[m][n];
  }

}

过程如下图所示

• 递推公式：f(x,y) = f(x-1,y) + f(x,y-1)
• 这道题跟公式里面是两个参数，所以在迭代时，采用的二维数组迭代，而上面的采用一维数组迭代
• 主要考虑公式里面变化的参数个数而选择不同维度的数组