西安博网站建设,网页制作与网站建设技术大全 pdf,苏宁电器网站建设特点分析,百度指数分析官网递归介绍 本来预算此章节是继续写快速排序的#xff0c;然而编写快速排序往往是递归来写的#xff0c;并且递归可能不是那么好理解#xff0c;于是就有了这篇文章。 在上面提到了递归这么一个词#xff0c;递归在程序语言中简单的理解是#xff1a;方法自己调用自己 递归其…递归介绍 本来预算此章节是继续写快速排序的然而编写快速排序往往是递归来写的并且递归可能不是那么好理解于是就有了这篇文章。 在上面提到了递归这么一个词递归在程序语言中简单的理解是方法自己调用自己 递归其实和循环是非常像的循环都可以改写成递归递归未必能改写成循环这是一个充分不必要的条件。 那么有了循环为什么还要用递归呢在某些情况下(费波纳切数列汉诺塔)使用递归会比循环简单很多很多话说多了也无益让我们来感受一下递归吧。我们初学编程的时候肯定会做过类似的练习 1234....100(n)求和给出一个数组求该数组内部的最大值我们要记住的是想要用递归必须知道两个条件 递归出口(终止递归的条件)递归表达式(规律)技巧在递归中常常是将问题切割成两个部分(1和整体的思想)这能够让我们快速找到递归表达式(规律) 一、求和 如果我们使用for循环来进行求和1234....100那是很简单的 int sum 0;for (int i 1; i 100; i) {sum sum i;}System.out.println(公众号Java3y sum);前面我说了for循环都可以使用递归来进行改写而使用递归必须要知道两个条件1、递归出口2、递归表达式(规律) 首先我们来找出它的规律123...n这是一个求和的运算那么我们可以假设X123...n可以将123...(n-1)看成是一个整体。而这个整体做的事又和我们的**初始目的(求和)**相同。以我们的高中数学知识我们又可以将上面的式子看成Xsum(n-1)n 好了我们找到我们的递归表达式(规律)它就是sum(n-1)n,那递归出口呢这个题目的递归出口就有很多了我列举一下 如果n1时那么就返回1如果n2时那么就返回3(12)如果n3时那么就返回6(123)当然了我肯定是使用一个最简单的递归出口了if(n1) return 1 递归表达式和递归出口我们都找到了下面就代码演示 递归出口为1 public static void main(String[] args) {System.out.println(公众号Java3y sum(100));}/**** param n 要加到的数字比如题目的100* return*/public static int sum(int n) {if (n 1) {return 1;} else {return sum(n - 1) n;}} 递归出口为4 public static void main(String[] args) {System.out.println(公众号Java3y sum(100));}/**** param n 要加到的数字比如题目的100* return*/public static int sum(int n) {//如果递归出口为4(1234)if (n 4) {return 10;} else {return sum(n - 1) n;}} 结果都是一样的。 二、数组内部的最大值 如果使用的是循环那么我们通常这样实现 int[] arrays {2, 3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 2};//将数组的第一个假设是最大值int max arrays[0];for (int i 1; i arrays.length; i) {if (arrays[i] max) {max arrays[i];}}System.out.println(公众号Java3y max);那如果我们用递归的话那怎么用弄呢首先还是先要找到递归表达式(规律)和递归出口 我们又可以运用1和整体的思想来找到规律 将数组第一个数-2与数组后面的数-{3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 2}进行切割将数组后面的数看成是一个整体X{3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 2}那么我们就可以看成是第一个数和一个整体进行比较if(2X) return 2 else(2X) return X而我们要做的就是找出这个整体的最大值与2进行比较。找出整体的最大值又是和我们的**初始目的(找出最大值)**是一样的也就可以写成if( 2findMax() )return 2 else return findMax()递归出口如果数组只有1个元素时那么这个数组最大值就是它了。使用到数组的时候我们通常为数组设定左边界和右边界这样比较好地进行切割 L表示左边界往往表示的是数组第一个元素也就会赋值为0(角标为0是数组的第一个元素)R表示右边界往往表示的是数组的长度也就会赋值为arrays.length-1长度-1在角标中才是代表最后一个元素)那么可以看看我们递归的写法了 public static void main(String[] args) {int[] arrays {2, 3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 1};System.out.println(公众号Java3y findMax(arrays, 0, arrays.length - 1));}/*** 递归找出数组最大的值* param arrays 数组* param L 左边界第一个数* param R 右边界数组的长度* return*/public static int findMax(int[] arrays, int L, int R) {//如果该数组只有一个数那么最大的就是该数组第一个值了if (L R) {return arrays[L];} else {int a arrays[L];int b findMax(arrays, L 1, R);//找出整体的最大值if (a b) {return a;} else {return b;}}}三、冒泡排序递归写法 在冒泡排序章节中给出了C语言的递归实现冒泡排序那么现在我们已经使用递归的基本思路了我们使用Java来重写一下看看 冒泡排序俩俩交换在第一趟排序中能够将最大值排到最后面外层循环控制排序趟数内层循环控制比较次数 以递归的思想来进行改造 当第一趟排序后我们可以将数组最后一位(R)和数组前面的数(L,R-1)进行切割数组前面的数(L,R-1)看成是一个整体这个整体又是和我们的**初始目的(找出最大值与当前趟数的末尾处交换)**是一样的递归出口当只有一个元素时即不用比较了LRpublic static void main(String[] args) {int[] arrays {2, 3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 1};bubbleSort(arrays, 0, arrays.length - 1);System.out.println(公众号Java3y arrays);}public static void bubbleSort(int[] arrays, int L, int R) {int temp;//如果只有一个元素了那什么都不用干if (L R) ;else {for (int i L; i R; i) {if (arrays[i] arrays[i 1]) {temp arrays[i];arrays[i] arrays[i 1];arrays[i 1] temp;}}//第一趟排序后已经将最大值放到数组最后面了//接下来是排序整体的数据了bubbleSort(arrays, L, R - 1);}} 四、斐波那契数列 接触过C语言的同学很可能就知道什么是费波纳切数列了因为往往做练习题的时候它就会出现它也是递归的典型应用。 菲波那切数列长这个样子{1 1 2 3 5 8 13 21 34 55..... n } 数学好的同学可能很容易就找到规律了前两项之和等于第三项 例如 1 1 22 3 513 21 34如果让我们求出第n项是多少那么我们就可以很简单写出对应的递归表达式了Z (n-2) (n-1) 递归出口在本题目是需要有两个的因为它是前两项加起来才得出第三项的值 同样地那么我们的递归出口可以写成这样if(n1) retrun 1 if(n2) return 2 下面就来看一下完整的代码吧 public static void main(String[] args) {int[] arrays {1, 1, 2, 3, 5, 8, 13, 21};//bubbleSort(arrays, 0, arrays.length - 1);int fibonacci fibonacci(10);System.out.println(公众号Java3y fibonacci);}public static int fibonacci(int n) {if (n 1) {return 1;} else if (n 2) {return 1;} else {return (fibonacci(n - 1) fibonacci(n - 2));}} 五、汉诺塔算法 图片来源百度百科 玩汉诺塔的规则很简单 有三根柱子原始装满大小不一的盘子的柱子我们称为A还有两根空的柱子我们分别称为B和C(任选)最终的目的就是将A柱子的盘子全部移到C柱子中 移动的时候有个规则一次只能移动一个盘子小的盘子不能在大的盘子上面(反过来大的盘子不能在小的盘子上面)我们下面就来玩一下 只有一个盘子 将A柱子的盘子直接移动到C柱子中完成游戏只有两个盘子 将A柱子上的小盘子移动到B柱子中将A柱子上的大盘子移动到C柱子中最后将在B柱子的小盘子移动到C柱子大盘子中完成游戏只有三个盘子 将A柱子小的盘子移动到C柱子中将A柱子上的中盘子移动到B柱子中将C柱子小盘子移动到B柱子中盘子中将A柱子的大盘子移动到C柱子中将B柱子的小盘子移动到A柱子中将B柱子的中盘子移动到C柱子中最后将A柱子的小盘子移动到C柱子中完成游戏 ....................... 从前三次玩法中我们就可以发现的规律 想要将最大的盘子移动到C柱子就必须将其余的盘子移到B柱子处(借助B柱子将最大盘子移动到C柱子中[除了最大盘子将所有盘子移动到B柱子中])[递归表达式]当C柱子有了最大盘子时所有的盘子在B柱子。现在的目的就是借助A柱子将B柱子的盘子都放到C柱子中(和上面是一样的已经发生递归了)当只有一个盘子时就可以直接移动到C柱子了(递归出口) A柱子称之为起始柱子B柱子称之为中转柱子C柱子称之为目标柱子从上面的描述我们可以发现起始柱子、中转柱子它们的角色是会变的A柱子开始是起始柱子第二轮后就变成了中转柱子了。B柱子开始是目标柱子第二轮后就变成了起始柱子。总之起始柱子、中转柱子的角色是不停切换的)简单来说就分成三步 把 n-1 号盘子移动到中转柱子把最大盘子从起点移到目标柱子把中转柱子的n-1号盘子也移到目标柱子那么就可以写代码测试一下了(回看上面玩的过程) public static void main(String[] args) {int[] arrays {1, 1, 2, 3, 5, 8, 13, 21};//bubbleSort(arrays, 0, arrays.length - 1);//int fibonacci fibonacci(10);hanoi(3, A, B, C);System.out.println(公众号Java3y );}/*** 汉诺塔* param n n个盘子* param start 起始柱子* param transfer 中转柱子* param target 目标柱子*/public static void hanoi(int n, char start, char transfer, char target) {//只有一个盘子直接搬到目标柱子if (n 1) {System.out.println(start ---- target);} else {//起始柱子借助目标柱子将盘子都移动到中转柱子中(除了最大的盘子)hanoi(n - 1, start, target, transfer);System.out.println(start ---- target);//中转柱子借助起始柱子将盘子都移动到目标柱子中hanoi(n - 1, transfer, start, target);}} 我们来测试一下看写得对不对 参考资料 https://www.zhihu.com/question/24385418六、总结 递归的确是一个比较难理解的东西好几次都把我绕进去了.... 要使用递归首先要知道两件事 递归出口(终止递归的条件)递归表达式(规律)在递归中常常用”整体“的思想在汉诺塔例子中也不例外将最大盘的盘子看成1上面的盘子看成一个整体。那么我们在演算的时候就很清晰了将”整体“搬到B柱子将最大的盘子搬到C柱子最后将B柱子的盘子搬到C柱子中 因为我们人脑无法演算那么多的步骤递归是用计算机来干的只要我们找到了递归表达式和递归出口就要相信计算机能帮我们搞掂。 在编程语言中递归的本质是方法自己调用自己只是参数不一样罢了。 最后我们来看一下如果是5个盘子要运多少次才能运完 PS:如果有更好的理解方法或者我理解错的地方大家可以在评论下留言一起交流哦 如果文章有错的地方欢迎指正大家互相交流。习惯在微信看技术文章想要获取更多的Java资源的同学可以关注微信公众号:Java3y 转载于:https://www.cnblogs.com/Java3y/p/8610134.html
