递归浅谈
谈及递归问题，大家第一印象肯定是汉诺塔问题或者斐波那契数列问题，当然了，如果你是一位LeetCode爱好者，肯定遇到了许多递归问题或者递归的变形问题。递归问题的求解主要是把一个大问题分解为子问题，但在计算子问题的时候，重复计算了大量的子问题。那么什么是递归呢，具体什么时候用呢？请容我一一道来， 维基百科中明确给出了递归的定义，即递归(Recursion)是指在函数的定义中使用函数自身的方法。也就是函数内部存在着调用函数本身的情况，这种现象即为递归。所以，既然明确了递归的定义，那么什么时候使用呢？在应用递归方法求解问题时，当该问题可以分解成具有相同解决方案的子问题，甚至是子子问题的时候，换言之，所有的这些问题都调用同一个功能函数，这个时候可以使用递归的方法求解，当然了，需要注意的是求解的问题最后必须是有一个固定值的，即存在递归终止条件，否则，该问题无解。经过判断问题是否可以用递归后，接下来便是递归求解思路(满满套路)，第一步，根据问题需求，定义递归函数，即明确函数功能；第二步，寻找问题与子问题之间的关联关系，即递归公式；第三步，使用数学表达式表示递归公式，并将写入递归函数中；第四步，根据问题与子问题的关联关系，推导计算时间复杂度并优化。
在这里，我们使用递归方法求解斐波那契数列数列问题进行阐明，求解斐波那契数列问题递归C++代码如下
int fb(int n) { if (n <= 2) return 1; return fb(n - 1) + fb(n - 2); }
虽然代码很简洁，但这段代码存在一个致命问题，当n很大时，求解斐波那契数将耗费大量的时间，这是因为很多数都被重复计算了，比如计算fb(10)的时候，需要计算fb(9)和fb(8)。于是，递归分别独立的去计算fb(9)和fb(8)，但是fb(9)和fb(8)的子问题，在计算fb(9)的时候，就已经计算出来了fb(8)，但这个结果未保存，所以在计算fb(8)的时候，又要重新计算一次，这样计算下来浪费了大量的时间。
递归变形记
既然我们发现了递归求解存在的问题，那么就要着手解决它，可以发现，递归存在大量的重复计算，那么，如果我们将计算的子问题的结果进行缓存一下，是不是就可以了，当然是滴！比如对于上面的递归问题，我们使用以为数组作为缓存表，修改上述代码，可以得到优化后的递归代码
nt fb(int n, vector<int > &dp) { if (dp[n] != -1) return dp[n]; if (n == 0) return 0; if (n == 1) return 1; int res = fb(n - 1, dp) + fb(n - 2, dp); dp[n] = res; return res; }
当然了，对于递归问题的优化除了使用缓存表外，还可以直接使用动态规划的方式解决。递归是自顶向下求解问题，而动态规划则是自底向上求解问题，所以，我们将缓存冗余的计算结果的计算过程，变为自底向上的过程就是动态规划求解方式。
举个栗子
最长公共子序列(LCS)求解问题
LCS定义：最长公共子序列问题是在一组序列中找到最长公共子序列，需要注意的是不同于子串问题，即LCS不需要是连续的子串。
LCS示例：
示例1
输入："ABCD"和"EDCA"
输出：1
解释：LCS是"A"或"C"或"D"
示例2
输入："ABCD"和"EACB"
输出：2
解释：LCS是"AC“
LCS实现(C++)
case1：暴力递归
/*暴力递归*/ int search1(int ida, int idb) { if (ida > len_a || idb > len_b) return 0; if (ida == len_a && idb == len_b) return 0; int res = INT_MIN; if (a[ida] == b[idb]) { res = search1(ida + 1, idb + 1) + 1; } return mymax(res, search1(ida + 1, idb), search1(ida, idb + 1)); }
case2：缓存表优化
/*缓存表优化*/ int dp[len_a][len_b]; int search2(int ida, int idb) { if (ida > len_a || idb > len_b) return 0; if (ida == len_a && idb == len_b) return 0; if (dp[ida][idb] != -1) return dp[ida][idb]; else { int res1 = INT_MIN; if (a[ida] == b[idb]) { res1 = search2(ida + 1, idb + 1) + 1; } int res2 = search2(ida + 1, idb); int res3 = search2(ida, idb + 1); int res = mymax(res1, res2, res3); dp[ida][idb] = res; return res; } }
case3：动态规划
/*动态规划*/ int search3(int ida, int idb) { //初始化最末行 for (int j = len_b - 1; j >= 0; j--) { if (b[j] != a[len_a - 1]) dp[len_a - 1][j] = 0; else { for (int k = 0; k <= j; k++) { dp[len_a - 1][k] = 1; } break; } } //初始化最右列 for (int i = len_a - 1; i >= 0; i--) { if (a[i] != b[len_b - 1]) dp[i][len_b - 1] = 0; else { for (int k = 0; k <= i; k++) { dp[k][len_b - 1] = 1; } break; } } for (int i = len_a - 2; i >= 0; i--) { for (int j = len_b - 2; j >= 0; j--) { int res1 = INT_MIN; if (a[i] == b[j]) res1 = dp[i + 1][j + 1] + 1; int res2 = dp[i+1][j]; int res3 = dp[i][j+1]; int res = mymax(res1, res2, res3); dp[i][j] = res; } } return dp[0][0]; }
小结
大家通过求解最长公共子序列的问题，是不是对递归的求解有了更深入的了解呢？对于一个问题，我们可以先从暴力算法开始，然后再从暴力的算法中寻找优化方案，这样下来，问题的实现方案必定更加完美。对于求解递归问题，我们先使用暴力破解，然后从暴力的算法里面找冗余的计算，找到冗余之后使用缓存表保存冗余的计算结果，这样就避免了暴力递归导致的冗余问题。
ps：求解最长公共子序列LCS完整源码：https://github.com/0625wzw/Algorithm/blob/master/%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97(LCS)