递推和递归：一个自下而上，一个自上而下

解决问题的思路不同

递推和递归是常见的解决问题的思路，在很多算法中都会用到，例如DFS算法基于递归实现，动态规划算法基于递推实现。

递推是从上到下解决问题，如想知道一个国家有多少人，我们从村这个一个行政级别开始，依次向上汇报，最后到国这个级别就能知道一个国家有多少人

递归是从上到下解决问题，如想知道一个国家有多少人。国家发布命令让各个省上报各自的人数，各个省又发布命令让各自市上报各自的人数，依次类推，最后到达村这个级别，开始统计自己的人数（递推出口），统计完后逐级上报，最后到国这个级别就能知道一个国家有多少人

爬楼梯

题目来源：Leetcode 70 题目描述：

我们依次从第1阶开始依次计算方法，第1阶有1种方法，第2阶有2种方法，那么第3阶呢？

第3阶只能从第1阶或者第2阶踏过来，所以到第3阶的方法数为到第1阶或者到第2阶的方法数之和。 第4阶只能从第2阶或者第3阶踏过来，所以到第4阶的方法数为到第2阶或者到第3阶的方法数之和。

依次类推dp[i] = d[i - 1] + dp[i - 2]（dp[i]为到第i阶的方法数）

学了动态规划后，你就能会发现递推就是简单版的动态规划

public int climbStairs(int n) {
    if (n == 1 || n == 2) {
        return n;
    }
    int[] dp = new int[n + 1];
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

我们用递推的思路来写一下实现，到n阶的方法数为到n-1阶和到n-2阶的和，递归的出口是第1阶有1种方法，第2阶有2种方法。

public int climbStairs(int n) {
    if (n == 1 || n == 2) {
        return n;
    }
    return climbStairs(n - 1) + climbStairs(n - 2);
}

在大多数情况下，递推解决问题的思路比较简单，代码也比较简洁，但是效率比较低（函数调用），同时也会有很多重叠子问题。递推的实现思路比较复杂，但是效率比较高。 参见二叉树的前中后序的递归调用和非递归调用

如图，当通过递归的方式求到第5级台阶的方法数时，到第3级台阶的方法数被算了2次，所以我们可以使用额外空间将结算得到的结果缓存下来，避免重复计算（即备忘录算法）

class Solution {

    // 数组大小按照题目的n确定
    int[] visit = new int[100];

    public int climbStairs(int n) {
        if (visit[n] != 0) {
            return visit[n];
        }
        if (n == 1 || n == 2) {
            return n;
        }
        visit[n] = climbStairs(n - 1) + climbStairs(n - 2);
        return visit[n];
    }

}

不同路径

来源：LeetCode 62 描述： 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。问总共有多少条不同的路径？

思路：这个大家一下就会想到用递归解决，假设f(m,n)表示移动到点(m,n)的路径数，因为机器人智能向下或者向右移动，所以点(m,n)只能从点(m-1,n)和(m,n-1)移动而来，递归公式就是f(m,n)=f(m-1,n)+f(m,n-1)，递归的出口呢？当然就是网格的边界了，网格边界上的点都只有一种方法，按照这种思路写出来如下代码

class Solution {
   public int uniquePaths(int m, int n) {
       // 在网格边界的格子只能有一种走法
       if (m == 1 || n == 1) {
           return 1;
       }
       // m，n这个位置只能从(m - 1 , n)和(m, n - 1)移动而来
       return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
   }
}

其实这个代码效率还是很低的，因为有很多重复的计算，如下图 当m和n为(3,3)时，(2,2)被计算了2次，而且m和n越大，重复计算的次数最多，我们可以把已经算出来的值保存一下，这样下次再用的时候就不用算了，直接取就行，叫做备忘录算法，grid[m][n]表示走到（m,n）这个点时的路径数。

class Solution {
   
   public static int[][] grid = new int[110][110];

   public int uniquePaths(int m, int n) {
       if (grid[m][n] != 0)
           return grid[m][n];
       if (m == 1 || n == 1) {
           return 1;
       }
       return grid[m][n] = uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
   }
}

当值不为0的时候说明已经被算过了，直接取就行了，否则就得计算并保存结果，这样效率提高了不少，但是如果m和n特别大，递归层数过多时会造成堆栈溢出的，该怎么办？这个时候就得用到动态规划了

递归是从上至下开始计算的，有没有可能从下而上的计算呢？，如先算出（1，2）和（2，1），然后就能算出（2，2）了，我们得按照一定的规律计算，保证在算（2，2）之前，（1，2）和（2，1）已经算完了，我们只要按行从左到右计算，或者按列从上到下即可

dp[i][j]表示到达第i行第j列的路径数，所以状态转移方程为

dp[i][j] = dp[i][j-1] + dp[i-1][j]

class Solution {

   public static int[][] grid = new int[110][110];

   public int uniquePaths(int m, int n) {

       for (int i = 1; i <= n ; i++) {
           for (int j = 1; j <= m ; j++) {
               if (i == 1 || j == 1)
                   grid[i][j] = 1;
               else
                   grid[i][j] = grid[i][j-1] + grid[i-1][j];
           }
       }
       return grid[n][m];
   }
}

数的计算

题目地址：洛谷 p1028 题目描述：

int main() {
    int n;
    cin >> n;
    int dp[n + 1];
    for (int i = 1; i <= n; ++i) {
        dp[i] = 1;
        for (int j = 1; j <= i / 2; ++j) {
            dp[i] += dp[j];
        }
    }
    cout << dp[n] << endl;
    return 0;
}

传球游戏

题目地址：洛谷 p1057 题目描述：

#include <iostream>
using namespace std;

const int MAX_N = 30;
int dp[MAX_N + 5][MAX_N + 5] = {0};

int main() {
    int n, m;
    cin >> n >> m;
    dp[0][1] = 1;
    for (int i = 1; i <= m; ++i) {
        for (int j = 2; j <= n - 1; ++j) {
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
        }
        dp[i][1] = dp[i - 1][2] + dp[i - 1][n];
        dp[i][n] = dp[i - 1][1] + dp[i - 1][n - 1];
    }
    cout << dp[m][1] << endl;
    return 0;
}