前情提要
上一篇递归算法讲解在这里
递归算法讲解（结合内存图）
没看过的小伙伴可以进去瞅一眼，谢谢！
递归算法的重要性
递归算法是非常重要的，如果想要进大厂，以递归算法为基础的动态规划是必考的，所以我们一定要好好学习递归算法！
本篇博客继续讲解一些递归的经典demo
demo01
递归实现求int类型的数组arr中前n项和，其中arr.length>=n，并且arr当中的元素总和在[-2147483648, 2147483647]之间
还记得递归三步走吗，我们来回顾一下
1. 明确递归的参数和返回值
很显然递归的参数有两个：数组arr + 要求和的序列长度n；
递归的返回值是我们求得的和，不会超过int类型的取值范围，所以数组求和很明显还是int
2. 明确递归的终止条件
我们已知的部分当中，n最小的情况就是递归的终止条件
我们目前已知的，sum(1)肯定是知道的，等于arr[0];sum(2)也是知道的，等于arr[0]+arr[1]；
1比较小，所以n==1就是递归的终止条件
递归就是循环，递归的终止条件就是循环的中止条件
还有一些诸如i==j，i>j，都可能称为递归中止条件
3. 明确递归的单层递归逻辑
递归的单层递归逻辑是最难想到的
其实明确单层递归逻辑，很像是中学数学中，让我们求数列的通项公式，我们需要找规律
假设arr = {3，4，7，1，8，12，47……}
sum(1) = 3，sum(2) = 7，sum(3) = 14，sum(4) = 15……
那么sum(n) = ？
差不多是这样的一个过程
当然，本题目是比较简单的，一眼就能看出来，sum(n) = sum(n-1) + arr[n - 1]
递归难就难在，我们很多时候看不出来这个递归逻辑，此时就需要罗列出来找规律
从结束到开始，从部分到整体，从具象到抽象……
代码
public static void main(String[] args) {
int[] arr = {3, 4, 7, 1, 8, 12, 47};
System.out.println(sum(arr, 5));
}
// 返回类型是int, 参数类型是arr和n
public static int sum(int[] arr, int n) {
// 前0项和显然是0
if (n == 0) {
return 0;
}
// 递归终止条件，返回arr[0]
if (n == 1) {
return arr[0];
}
// 单层递归逻辑，需要注意要加上arr[n-1]而不是arr[n]，因为数组的下标是[0, arr.length - 1]
return sum(arr, n - 1) + arr[n - 1];
}
输出结果
demo02
递归实现折半查找
1. 明确递归的参数和返回值
递归参数是数组arr和要查找的值val
以及left，mid，right三个arr下标，用于判断后的移动
返回类型，可以返回找到的数值的下标（int），也可以什么都不返回（void）
2. 明确递归的终止条件
很明显是arr[i] = val，但是我们用谁去充当这个i指针呢？
熟悉折半查找的同学都知道，折半查找需要至少3个指针：left，mid，right
每一个指针都有可能在移动过程中直接指向val，我们应该选择谁当指针i呢？
很明显是mid，mid可以代表所有情况，left和right就不一定，而且可能陷入死循环
比如arr[mid]正好指向val，但是arr[left] != val，那么就会出现，arr[mid]既不大于val，也不小于
mid，但是无法跳出while循环的情况，也就是死循环
3. 明确递归的单层递归逻辑
当arr[mid] != val时执行递归
如果arr[mid]>val，说明val在mid左边，递归到左区间寻找；
如果arr[mid]<val，说明val在mid右边，递归到右区间寻找。
代码
public static void main(String[] args) {
// 折半查找的前提是数组有序
int[] arr = {1, 4, 34, 51, 432, 1111, 2776};
halfSearch(arr, 4, 0, 3, arr.length - 1);
}
public static void halfSearch(int[] arr, int val, int left, int mid, int right) {
if (val == arr[mid]) {
System.out.println(val + "找到了,下标是：" + mid);
return; }
if (val > arr[mid]) {
halfSearch(arr, val, mid, (right + mid) / 2, right);// mid + 1也行
} else if (val < arr[mid]) {// else即可
halfSearch(arr, val, left, (mid + left) / 2, mid);// mid - 1也行
}
}
此时就会有聪明的小伙伴问了，如果没找到呢，你这种写法会栈溢出啊
其实我们只需要给left和right加一个判断就可以了
public static void main(String[] args) {
// 折半查找的前提是数组有序
int[] arr = {1, 4, 34, 51, 432, 1111, 2776};
halfSearch(arr, 432, 0, 3);
}
public static int halfSearch(int[] arr, int val, int left, int right) {
int mid = (left + right) / 2;
if (val == arr[mid]) {
System.out.println(val + "找到了,下标是：" + mid);
return mid;
}
if (left <= right) {
if (val > arr[mid]) {
return halfSearch(arr, val, mid + 1, right);// mid + 1也行
} else {// else即可
return halfSearch(arr, val, left, mid - 1);// mid - 1也行
}
} else {
System.out.println(val + "没找到！");
return -1;
}
}
如果left都大于right了，arr[mid]还是不等于val，那就说明真的没有这个值
demo03
二叉树的中序遍历
左，根，右---------------->中序遍历
如果一个要访问的结点，存在左子树，那么先访问左子树的最左结点
1. 明确递归的参数和返回值
递归参数是二叉树TreeNode，我们叫它root
返回类型，void即可，我们在遍历途中打印每一个结点的val值即可
2. 明确递归的终止条件
root不断遍历，只要不是空，就可以一直遍历
3. 明确递归的单层递归逻辑
上图这棵树，中序遍历的结果是7，37，13，46，3，19，76，48
因为树是链式结构，我们要遍历一棵树，只能先从根节点开始遍历，不能跨越访问，只能root.left.left……这样访问，这样就令很多同学犯难，我要怎么先从7开始访问呢？
这里其实非常简单，不要想的太复杂
我们仍然先从根节点开始访问，然后访问左子树，最后访问右子树
但是我们在访问左子树结束后再打印，我们只需要保证打印顺序是左根右即可
伪代码（不能运行！！！）
public static void middle(TreeNode root) {
if (root == null) {
return;
}
// root不是null，先判断左孩子是不是null，再判断右孩子是不是null
middle(root.left);
System.out.println(left.val);
middle(root.right);
}
