我想大家在最初学习数组的时候就应该见识到递归了。但是呢大家也不会在意这个东西，就通过老师讲的：递归就是自己调自己！
我当时听到这句话就觉得自己行了，递归就是自己调自己也没啥厉害的地方，也就没在意。后面随着自己有去做一些关于算法类的题目时才发现递归就是递归，它是自己调自己但是还是不会用啊。
我想很多人应该跟我有一样的感受，那么我们现在一起来重新学习一下递归！
public void recursion(参数一) {
if (终止条件) {
return;
}
recursion(参数二);
}
以上就是递归最简洁的模板了，它有两个需要我们主要的地方第一个是终止条件(这个是最重要的)，第二个是自己调自己(最能体现递归思想)，有了这两个才算递归。
这就算升级版的递归模板了，看到这里我相信大家和我一样也是很懵了，到底什么是递归啊？讲真的，递归说白了就是一句话：自己调自己！通过一个概念性的描述我想大家各和我一样还是不理解什么是递归，那么我们可以尝试通过一些简单的题目用递归来做从而体会递归的真正含义。
斐波那契数列递归题目有很多，我们就从最简单也是最经典的斐波那契数列来进行演示吧。斐波那契数列我想在高中学习数列的时候我们大家都应该做过这道题，当时只知道高考拿分还不知道这道题还可以用代码计算出来。
什么是斐波那契数列：
斐波那契数列指的是这样一个数列：1，1，2，3，5，8，13，21，34，55，89...
这个数列从第3项开始，每一项都等于前两项之和。如果设f(n)为该数列的第n项,那么这句话可以写成如下形式：f(n) = f(n-1) + f(n-2)。那么我们用代码演示一下。
public static int fibonacci(int n) {//参数n:需要求的第几项
if (n == 1 || n == 2) {//终止条件
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);//递归调用(自己调自己)
}
上面代码演示了最简单也是最经典的斐波那契数列，代码中的终止条件是最重要的，这是我们递归结束的指令。如果我们的终止条件设置错误或者忘记写了，程序会一直执行如死循环一样，直至出现堆栈溢出异常(StackOverflowError)。类似如斐波那契数列这样经典的题目还有汉诺塔问题，在这就不过多描述了。
往下稍微升级一下该模板，让其可以完成一些稍微难的递归题目。
public void recursion(参数一) {
if (终止条件) {
return;
}
逻辑运算1
recursion(参数二);
逻辑运算2
recursion(参数三);
逻辑运算3
recursion(参数四);
}
随着模板升级变多我们也来升级一下题目，接着和大家共同学习一个机器人问题。
机器人问题 假设有排成一行的N个位置,记为1~N,N一定大于或等于2
* 开始时机器人在其中的M位置上(M一定是1~N中的一个)
* 如果机器人来到1位置,那么下一步只能往右走来到2位置;
* 如果机器人来到N位置,那么下一步只能往左来到N-1位置;
* 如果机器人来到中间位置,那么下一步可以往左走或者往右走;
* 规定机器人必须走K步,最终能来到P位置(P也是1~N中的一个)的方法有多少种
* 给定四个参数N,M,K,P,返回方法数。
假设有4个位置记作1~4，机器人现在在2号位置上；需要走4步；目标是走到4；可以走4步。问有几种走法？在面对这种题我们可以先手算出有几种方法然后在通过代码逐渐实现，现在我们省略手算部分直接上代码体会！
public class RobotTest {
public static int ways1(int N, int start, int aim, int K) {
//start:从什么地方开始 K:还需要走几步 aim:目标 N:可以走几步
return process1(start, K, aim, N);
}
// 机器人当前来到的位置是cur
// 机器人还有rest步需要走
// 最终目标是aim
// 有那些位置1~N
// 返回:机器人从cur出发,走过rest步之后,最终停在aim的方法数,是多少
public static int process1(int cur, int rest, int aim, int N) {
if (rest == 0) {// 如果步数走完了,机器人当前位置正好是aim返回一种,如果不是就返回0.
return cur == aim ? 1 : 0;
}
// rest > 0 ,还有步数要走
if (cur == 1) {// 1 --> 2 在最左边只能往右边走
return process1(2, rest - 1, aim, N);
}
if (cur == N) {// N --> N-1 在最右边只能往左边走
return process1(N - 1, rest - 1, aim, N);
}
// 中间位置
return process1(cur - 1, rest - 1, aim, N) + process1(cur + 1, rest - 1, aim, N);
}
public static void main(String[] args) {
System.out.println(ways1(2, 4, 4, 4)+"种方法");
}
通过上述代码我们可以体会到升级版的递归模板，依旧少不了终止条件，自己调自己。这就是递归！在以后我们遇到类似的题目考虑可以使用递归时，直接套模板。最关键的是需要寻找问题的终止条件，其次找到问题中的等价关系式也就是自己调自己！
往下在走几步递归往下进行的应该就到动态规划了，本篇主要的是讲一下我个人(初学者)对递归的看法。但是我们可以往下走几步到动态规划，这里就不演示了看看机器人问题往下研究的代码。
public static int ways2(int N, int start, int aim, int K) {
int[][] dp = new int[N + 1][K + 1];
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= K; j++) {
dp[i][j] = -1;
}
}
// dp就是缓存表 N+1 * K+1 规模的缓存表
// dp[cur][rest] == -1 -->表示process2(cur,rest)之前没有算过
// dp[cur][rest] != -1 -->表示process2(cur,rest)之前算过
return process2(start, K, aim, N, dp);
}
// cur的范围:1 ~ N
// rest的范围:0 ~ K
public static int process2(int cur, int rest, int aim, int N, int[][] dp) {
if (dp[cur][rest] != -1) {
return dp[cur][rest];
}
int ans = 0;
if (rest == 0) {
ans = cur == aim ? 1 : 0;
} else if (cur == 1) {
ans = process2(2, rest - 1, aim, N, dp);
} else if (cur == N) {
ans = process2(N - 1, rest - 1, aim, N, dp);
} else {
ans = process2(cur - 1, rest - 1, aim, N, dp) + process2(cur + 1, rest - 1, aim, N, dp);
}
dp[cur][rest] = ans;
return ans;
}
总结
递归说白了还是自己调自己！但是在处理问题是我们需要找到问题中的终止条件，问题中的等价关系式，通过模板来套用达到处理该问题的目的。
//本篇代码学习自B站：左神。左神真的特牛！如果侵权请联系我会及时删除。
