东莞市住房和城乡建设局网站,trswcm网站建设,晋中seo,长沙网站 建设推广世云网络前情提要
上一篇递归算法讲解在这里 递归算法讲解#xff08;结合内存图#xff09;
没看过的小伙伴可以进去瞅一眼#xff0c;谢谢#xff01;
递归算法的重要性
递归算法是非常重要的#xff0c;如果想要进大厂#xff0c;以递归算法为基础的动态规划是必考的…前情提要
上一篇递归算法讲解在这里 递归算法讲解结合内存图
没看过的小伙伴可以进去瞅一眼谢谢
递归算法的重要性
递归算法是非常重要的如果想要进大厂以递归算法为基础的动态规划是必考的所以我们一定要好好学习递归算法
本篇博客继续讲解一些递归的经典demo
demo01
递归实现求int类型的数组arr中前n项和其中arr.lengthn并且arr当中的元素总和在[-2147483648, 2147483647]之间
还记得递归三步走吗我们来回顾一下 1. 明确递归的参数和返回值 很显然递归的参数有两个数组arr 要求和的序列长度n 递归的返回值是我们求得的和不会超过int类型的取值范围所以数组求和很明显还是int 2. 明确递归的终止条件 我们已知的部分当中n最小的情况就是递归的终止条件
我们目前已知的sum(1)肯定是知道的等于arr[0];sum(2)也是知道的等于arr[0]arr[1]
1比较小所以n1就是递归的终止条件
递归就是循环递归的终止条件就是循环的中止条件
还有一些诸如ijij都可能称为递归中止条件 3. 明确递归的单层递归逻辑 递归的单层递归逻辑是最难想到的
其实明确单层递归逻辑很像是中学数学中让我们求数列的通项公式我们需要找规律 假设arr {347181247……} sum(1) 3sum(2) 7sum(3) 14sum(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和npublic static int sum(int[] arr, int n) {// 前0项和显然是0if (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
以及leftmidright三个arr下标用于判断后的移动
返回类型可以返回找到的数值的下标int也可以什么都不返回void 2. 明确递归的终止条件 很明显是arr[i] val但是我们用谁去充当这个i指针呢
熟悉折半查找的同学都知道折半查找需要至少3个指针leftmidright
每一个指针都有可能在移动过程中直接指向val我们应该选择谁当指针i呢
很明显是midmid可以代表所有情况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. 明确递归的单层递归逻辑 上图这棵树中序遍历的结果是73713463197648
因为树是链式结构我们要遍历一棵树只能先从根节点开始遍历不能跨越访问只能root.left.left……这样访问这样就令很多同学犯难我要怎么先从7开始访问呢
这里其实非常简单不要想的太复杂
我们仍然先从根节点开始访问然后访问左子树最后访问右子树
但是我们在访问左子树结束后再打印我们只需要保证打印顺序是左根右即可
伪代码不能运行 public static void middle(TreeNode root) {if (root null) {return;}// root不是null先判断左孩子是不是null再判断右孩子是不是nullmiddle(root.left);System.out.println(left.val);middle(root.right);}
