江苏省建设厅网站挂证存疑名单,合肥备案,南昌网站开发,合肥网络推广有限公司递归
1.基础简介 递归在计算机科学中#xff0c;递归是一种解决计算问题的方法#xff0c;其中解决方案取决于同一类问题的更小子集 例如 递归遍历环形链表 基本情况#xff08;Base Case#xff09;#xff1a;基本情况是递归函数中最简单的情况#xff0c;它们通常是递…递归
1.基础简介 递归在计算机科学中递归是一种解决计算问题的方法其中解决方案取决于同一类问题的更小子集 例如 递归遍历环形链表 基本情况Base Case基本情况是递归函数中最简单的情况它们通常是递归终止的条件。在基本情况下递归函数会返回一个明确的值而不再进行递归调用。递归情况Recursive Case递归情况是递归函数中描述问题规模较大的情况。在递归情况下函数会调用自身来解决规模更小的子问题直到达到基本情况。
优点
简洁清晰递归能够将复杂的问题简化成更小的子问题使得代码更加清晰易懂。问题建模递归能够自然地将问题建模成递归结构使得问题的解决变得更加直观。提高代码复用性通过递归可以在不同的情景中复用相同的解决方案。
缺点
性能损耗递归调用涉及函数的重复调用和堆栈的频繁使用可能会导致性能下降。内存消耗每次递归调用都需要在堆栈中存储函数的调用信息可能会导致堆栈溢出的问题。难以理解和调试复杂的递归调用可能会导致代码的难以理解和调试特别是递归函数中存在多个递归调用时。
常用场景
树和图的遍历树和图的结构天然适合递归的处理方式如深度优先搜索DFS。分治算法许多分治算法如归并排序和快速排序都是通过递归实现的。动态规划动态规划问题中递归可以帮助描述问题的递归结构但通常需要使用记忆化搜索或者自底向上的迭代方式来提高性能。排列组合问题许多排列组合问题如子集、组合、排列等可以通过递归实现。
/*** 递归进行遍历* param node 下一个节点* param before 遍历前执行的方法* param after 遍历后执行的方法* deprecated 递归遍历,不建议使用,递归深度过大会导致栈溢出。建议使用迭代器,或者循环遍历,或者使用尾递归,或者使用栈* see #loop(Consumer, Consumer)*/
public void recursion(Node node, ConsumerInteger before, ConsumerInteger after){// 表示链表没有节点了那么就退出(注意 环形链表的 末尾 不是null 而是头节点)if (node sentinel){return;}// 反转位置就是逆序了before.accept(node.value);recursion(node.next, before, after);after.accept(node.value);
}自己调用自己说明每一个函数对应着一种解决方案自己调用自己意味着解决方案是一样的或者说是有规律的每次调用函数处理的数据相对于上一次会缩减而且最后会缩减至无需继续递归内层函数调用子集处理完成外层函数才能调用完成
1.1.思路 首先需要确定自己的问题能不能用递归的思路去解决 然后需要推导出递归的关系父问题和子问题之间的关系 以及递归的中止条件 f ( n ) { 停止 , n n u l l f ( n , n e x t ) , n ≠ n u l l f(n) \begin{cases} 停止, n null \\ f(n,next), n \neq null \\ \end{cases} f(n){停止f(n,next),nnull,nnull
深入到最里层的 叫做递从最里层出来的叫做归在递过程中外层函数内的局部变量以及参数方法并未消失归的时刻还会用到。
2.案例
2.1.案例1-求阶乘
Test
DisplayName(测试-递归-阶乘)
public void test1(){int factorial factorial(5);logger.error(factorial :{},factorial);
}/*** 阶乘* param value 阶乘的值* return 阶乘的结果*/
public int factorial(int value){// 递归的终止条件if(value 1){return 1;}// 递归的公式 f(n) n * f(n-1)return value * factorial(value-1);
}2.2.案例2-字符串反转
递n从0开始每次都从都头部对字符串进行分割每次拼接的字符串只取第一位归从 str.length() 1开始归从归开始拼接自然是逆序的
# 思路递归的终止条件是字符串的长度为1, 递归的公式是 f(n) f(n-1) str.charAt(0) 从后往前拼接字符串/*** 反向打印字符串序列* param str 字符串* return 反向打印的字符串*/
public String reverse(String str){if(str.length() 1){return str;}logger.error(str.substring(1) {} , str.CharArt(0) {},str.substring(1),str.charAt(0));// substring(1) 从下标为1的位置开始截取字符串, chatAt(0) 获取下标为0的字符return reverse(str.substring(1)) str.charAt(0);
}Test
DisplayName(测试-递归-反向打印字符串序列)
public void test2(){String str abcdefg;String reverse reverse(str);logger.error(reverse :{},reverse);
}2.3.案例3-递归二分查找 /*** 二分查找* param source 原始数组* param target 目标值* param left 左边界* param right 右边界* return 目标值的索引位置*/public int binaryFind(int source[],int target,int left,int right){// 先找到中间值int mid (left right) 1;if (left right){// 如果left right 直接返回-1return -1;}if (source[mid] target){// 如果中间值小于目标值则在右边进行寻找return binaryFind(source,target,mid1,right);} else if(source[mid] target){// 如果中间值大于目标值 则在左边进行寻找return binaryFind(source,target,left,mid-1);} else {// 如果中间值等于目标值,则返回索引位置return mid;}}/*** 二分查找* param source 原始数组* param target 目标值* return 目标值的索引位置*/public int search(int[] source,int target){// 二分查找 递归的终止条件是 left rightreturn binaryFind(source,target,0,source.length-1);}TestDisplayName(测试-递归-二分查找)public void test3(){int[] source {1,2,3,4,5,6,7,8,9,10};int target 3;int index search(source,target);logger.error(index :{},index);}2.4.案例4-递归冒泡排序
递归冒泡排序原理
递归冒泡排序是一种排序算法它将数组分成已排序和未排序两部分。通过递归地比较相邻元素并交换它们的位置每次递归都将未排序部分的最大元素移到已排序部分的末尾直到整个数组有序。
实现思路
初始化将整个数组视为未排序部分。递归调用递归地调用 bubble_sort() 函数来处理未排序部分直到未排序部分长度为0或1排序结束。比较与交换在每次递归中从数组开始处向后遍历比较相邻元素。如果前一个元素大于后一个元素则交换它们的位置。更新未排序部分记录每次交换的位置即最后一次交换的索引作为下一次递归的边界确保下一次递归只需处理未排序部分的子数组。终止条件递归终止条件是未排序部分长度为0或1表示数组已排序完成。
可优化的地方及优势
优化点递归冒泡排序在每次递归中对未排序部分进行了全遍历可能导致效率较低尤其是对于大型数组。优势递归冒泡排序的主要优势在于其简洁易懂的实现方式易于理解和实现。
实现突出重点
递归调用通过递归调用 bubble_sort() 函数将排序过程分解为子问题直到基本情况未排序部分长度为0或1得到解决。边界更新每次递归后更新未排序部分的边界使下一次递归只需处理未排序部分的子数组。终止条件设定递归终止条件确保排序过程能够正确结束。
# 思路比较相邻的元素。如果第一个比第二个大就交换他们两个。对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对。在这一点最后的元素应该会是最大的数。针对所有的元素重复以上的步骤除了最后一个。持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较。
# 控制1递归每次重新划分排序的区间负责把已经排序的区间进行过滤2循环负责两两比较交换。/*** 递归冒泡排序* ul* li将数组划分成两部分[0,j] [j1,length - 1]/li* li[0,j] 左边是未排序的部分/li* li[j1,length - 1] 右边是已经排序的部分/li* li在未排序的区间内相邻的两个元素比较如果前一个元素大于后一个元素那么交换位置/li** /ul* param source*/public void sort (int [] source){bubble_sort(source,source.length-1);}/*** 递归冒泡排序* param source 待排序的数组* param j 未排序的区间的起始位置*/public void bubble_sort(int [] source,int j){// 递归的终止条件是数组的长度为1 或者数组的长度为0if (j 0){return;}// x充 未排序 和已经排序的分界线int x 0;// 每次都是从0开始for (int i 0; i j;i){// 如果前一个元素比后一个元素大那么交换位置if (source[i] source[i1]){int temp source[i];source[i] source[i1];source[i 1] temp;x i;}}// 递归调用(因为每次最大值都会移动到最后所以每次的排序区间都往前进行移动)bubble_sort(source,x-1);}TestDisplayName(测试-递归-冒泡排序)public void test4(){int[] source {4,3,2,1,5,6,7};sort(source);logger.error(source :{},source);}2.5.案例5-插入排序
插入排序原理
插入排序是一种直观的排序算法类似于整理扑克牌。它从未排序的部分选取元素并将其插入到已排序的序列中直到所有元素都排好序为止。
实现思路
这段代码使用递归来实现插入排序。在递归函数 insertion() 中每次调用时它从未排序的部分选择第一个元素 t source[low]然后将其插入到已排序的序列中的适当位置。
具体实现过程如下
从右向左遍历已排序的部分找到第一个比待插入元素小的位置。将比待插入元素大的元素往后移一位为待插入元素腾出空间。插入待排序元素到找到的位置插入位置为 i 1其中 i 是最后一个比待插入元素小的元素的下标。
递归终止条件
递归的终止条件是当 low 等于数组长度时表示所有元素都已处理完成无需继续排序。 /*** 插入排序* param source 原始数组*/
public void insert_sort(int[]source){// 递归调用插入排序 low 从1开始insertion(source,1);
}/*** 插入排序* param source 原始数组* param low 未排序数据的起始位置*/
private void insertion(int[]source,int low){// 递归的终止条件是 low source.lengthif(low source.length){return;}// 存储临时变量 存放low指向的数据int t source[low];// 已经排序区域的指针int i low -1;// 从右往左找只要找到第一个比t小的就能确认插入位置while (i 0 source[i] t ){// 如果没有找到插入位置 一直循环// 空出插入位置source[i1] source[i];i--;}// 找到了插入位置// 将t赋值给i 1 的位置就行了source[i 1] t;insertion(source,low 1);}Test
DisplayName(测试-递归-插入排序)
public void test5(){int[] source {2,4,5,10,7,1};insert_sort(source);logger.error(source :{},source);
} 多路递归
2.案例1-斐波那契数列
每个递归只包含一个自身的调用称之为single recursion如果每个递归函数包含多个自身的调用称为multi recursion f ( n ) { 0 , n 0 1 , n 1 f ( n − 1 ) f ( n − 2 ) , n 1 f(n) \begin{cases} 0, n 0 \\ 1, n 1 \\ f(n-1)f(n-2), n 1 \\ \end{cases} f(n)⎩ ⎨ ⎧01f(n−1)f(n−2),n0,n1,n1
TestDisplayName(测试-递归-斐波那契数列)public void test1(){int factorial factorial(10);logger.info(factorial:{},factorial);}/*** 斐波那契数列* param n 传入的参数* return 返回的结果*/public int factorial(int n){// 递归的出口当n为0时返回0当n为1或者2时返回if (n 0){return 0;}if (n 1 || n 2){return 1;}// 依次往下递归return factorial(n-1) factorial(n -2);}递归爆栈
1.分析 在Java中递归爆栈是指递归调用导致调用栈溢出的情况。在解释递归爆栈时我们可以涉及到Java的内存模型和变量存储位置的分析。 1.1 Java 内存模型
Java程序在运行时内存被划分为不同的区域其中涉及到
堆Heap用于存储对象实例由Java垃圾回收器进行管理和清理。栈Stack每个线程都有自己的栈用于存储局部变量、方法调用和部分对象引用。方法区Method Area存储类的结构信息、静态变量、常量等。程序计数器Program Counter记录线程执行的当前位置。
1.2. 递归的内存分析
在Java中每次方法调用都会在栈上分配一定的空间包括方法的参数、局部变量和返回地址。当一个方法被调用时会将当前方法的上下文包括参数、局部变量等推入栈中当方法执行结束时栈顶的帧会被弹出。
1.3. 递归爆栈的原因
递归函数在调用自身时会持续地将新的调用帧推入栈中如果递归调用的深度过大栈空间会耗尽导致栈溢出错误。
1.4. 变量存储位置分析
局部变量Local Variables在方法执行时局部变量存储在栈帧中并且随着方法的结束而被销毁。实例变量Instance Variables实例变量存储在对象的堆内存中随着对象的创建和销毁而分配和释放。静态变量Static Variables静态变量存储在方法区中它们在类加载时被初始化在程序结束时销毁。
2.代码
/*** 递归求和* param n 传入的参数* return 返回的结果*/
public int add(int n){if (n 1){return 1;}return add(n -1) n;
}Test
DisplayName(测试-递归-递归求和)
public void test2(){int sum add(11111110);logger.error(sum:{},sum);
}3.解决
# 目前只有C 和 scala 能针对尾递归优化所以我们一般需要将递归转为循环来写尾调用
// 如果函数的最后一步是调用一个函数那么成为尾调用
function a(){return b();
}// 下面这个 三段代码并不能称为尾调用
function a(){// 虽然调用了函数但是又用到了外层函数的数值1return b() 1;
}function a(){// 最后异步并非调用函数const c b() 1return c;
}function a(x){// 虽然调用了函数但是又用到了外层函数的数值xreturn b() x;
}4.总结
递归爆栈的问题通常发生在递归调用的深度过大时导致栈空间耗尽。通过合理控制递归调用深度、优化算法或者考虑使用迭代等方法可以避免这类问题在Java中局部变量和方法调用的栈帧管理是导致递归爆栈的关键因素之一。 递归是一种强大的问题解决工具能够简化问题、提高代码的清晰度和可读性。然而在使用递归时需要注意避免潜在的性能问题和堆栈溢出问题。选择适当的场景和合适的算法可以充分发挥递归的优势提高程序的效率和可维护性。
