您现在的位置是:首页 > 文章详情

递归学习

日期:2018-11-28点击:287
  • 说到递归,我心里真是有亿万只cnm...自己了解递归这个概念已经有一段时间了,但是一直灭有用过,今天说试试吧,结果写了个public void test(){}没然后了...
  • 所以这一篇文章是自己总结一下递归的知识,总结完之后回过头来自己的感觉是:编写递归不要深入到每次递归,因为容易陷进递归中,而是做一个指导者,将你的思路告诉递归,而循环就不一样,你必须告诉循环,每一步需要做什么怎么做,总结完本篇文章耗费不少时间,但是还是没有那种豁然开朗的问题,应该是还需要多加思考练习吧

小故事

  • 从前有座山,山上有座庙,庙里住着个老和尚,老和尚在跟小和尚讲故事,讲的是什么故事呢?:从前有座山,山上有座庙,庙里住着个老和尚,老和尚在跟小和尚讲故事,讲的是什么故事呢?...讲的是什么故事呢?:现在有个人在看我的文章(哈哈小时候最后一句可不是这个)
  • 上面讲了一个大家都知道的小故事,山套山,庙套庙,那么递归其实这个故事是很像的,递归也是一层一层的结构,自己调用自己,递归的条件是必须有一个出口,那么就是上面的:现在有个人在看我的文章,如果没有这个出口,那么递归会引发程序错误,递归就好像这样的

dedca4810dc386f38c34608e76a55b92

  • 看到上面的动图我们应该稍微对递归有一点认识了,但是上面的动图是没有出口的,他俩就这么傻乎乎的你看我看的,但是如果最后箱子里放着一张纸条:纸条上写着:穿黑衣服的是傻x,那么现在他俩肯定就不在是你看箱子我也看箱子了,而是开始结束这个过程,把箱子关上开始干架了
  • 从上面的描述:我们便可以稍微理解一下递归的定义了

百度百科:程序调用自身的编程技巧称为递归(recursion):递归,就是在运行的过程中调用自己

  • 如下一段代码

    //便于理解什么是自己调用自己 public void function(int i){ if (i == 1) { System.out.println(i); }else { function(i - 1); //自己调用自己 System.out.println(i); } }
  • 上面的代码是一个递归调用,实现的功能是打印1到i的值,那么他为什么会实现这样的功能呢?

markdown_img_paste_20181128142415427

  • 如上当我们的参数i输入为5的时候,执行结果如上图所示:首先判断i是否为1,no代表不是,然后进入代码中else部分,然后开始递归调用自己,这时候需要注意的是,程序已经开始递归调用自己了,所以下面的输出并没有执行,而是开始执行下一个递归调用的function,然后继续判断i,直到i为1的时候,判断为yes代表条件满足,开始执行满足i==1条件的输出语句,执行完毕输出1,然后这个方法已经没有其他语句需要执行了,因为他只满足i==1,而else是不满足的,所以此方法结束,但是他的上一个i==2的方法还没有结束,他执行到了function的递归调用了,这时候i==1结束后,i==2的方法才开始往下执行,输出i为2,然后i==2的方法执行完,由于它是i==3的方法调用的,所以现在轮到i==3的方法执行剩下语句,然后一步步往上返回直到调用的最顶端i==5
  • 如上递归也类似一种循环结构,但是与for或者其他循环结构不同的是,递归涉及到压栈和弹栈
  • 压栈:就是你的某个方法将要执行的时候,需要将它放入方法栈内去执行
  • 弹栈:就是你的某个方法执行结束了,他就要从方法栈移除

    public void test() { one(); } private void one() { two(); } private void two() { three(); } private void three() { four(); } private void four() { System.out.println("4"); }
  • 上面的代码很简单了,他就是调用调用再调用,然后我们早four方法的输出那打上断点,开始调试test,就会发现我们的编译器会给我们显示出他的方法栈内的方法的调用顺序

markdown_img_paste_20181128144009934

  • 如上的图片是截取IDEA给出的调用顺序,所以到这我们也就明白了,为啥他只能i==1的时候执行完毕之后才会执行i==2剩余操作了,因为i==1处于栈顶,i==1执行完毕弹栈走了,处于栈顶的才是i==2,所以会产生这样的效果
  • 好了到这,我们算是了解了递归的一个工作的方式,那么我们开始一些小的例子来学习递归

阶乘n!

  • 阶乘:如果是求5的阶乘为:5*4*3*2*1
  • 总结规律:n的阶乘为:n!=n*n(n-1)*n(n-2)..

    public int factorial(int n) { int sum = 0; //如果成立,代表了n==1了 if (n <= 1) { //出口 return 1; } //总结的公式 : n * (n-1) return n * factorial(n - 1); }
  • 因为1的阶乘就是1,所以出口设置为1,当运行了return 1;后,方法开始逐个弹栈完成运算

字符串反向输出

  • 利用Scanner一个一个输入然后利用一个结束标志#表示结束整个输入过程然后反向输出字符
  • 比如输入ABC#输出CBA

    public void reverseStr(Scanner scan) { System.out.println("input :"); String s = scan.nextLine(); if ("#".equals(s)){ return; }else { reverseStr(scan); System.out.println(s); } }
  • 结果

    input : A input : B input : C input : # C B A

递归文件夹

public void recursionFolder(String initPath) { //创建目录对象 File file = new File(initPath); //创建的时候File类并不判断路径是否存在,在这判断 if (file.exists()) { //列出文件夹下所有文件和文件夹 File[] files = file.listFiles(); for (File f : files) { if (f.isDirectory()){ //如果是文件夹,输出这个路径 System.out.println(f.getAbsolutePath()); //然后再去递归调用,遍历此文件夹 recursionFolder(f.getAbsolutePath()); }else { //代表是文件,直接输出 System.out.println(f.getAbsolutePath()); } } } }

斐波那契数列

  • 不要被名字吓到,其实就是类似兔子生孩子的问题
  • 问题描述:有一对兔子,第一个月一对兔子搬到新家,第二个月安顿好了开始你侬我侬蹦擦擦,然后第三个月就诞生了一对兔子,诞生的这对新的兔子依旧是第一个月搬走,第二个月开始你侬我侬蹦擦擦,第三个月才开始生崽,如下图

markdown_img_paste_20181128160721835

  • 如上,一个颜色的,就是原来的那对兔子,都是在第三个月生下一对兔子,如果兔子不死,那么第n个月应该有多少对兔子
  • 我们先分析一下数量之间的规律

markdown_img_paste_20181128161000636

  • 如上观察到,当第一第二月的时候,兔子还没有生下新兔子,所以是一对,从第三个月开始,在第一个月就出生的兔子开始当爸妈生下小兔子,而第二个月新兔子并没有到两个月他们还不能生育,所以第三个月是两对兔子=老兔子+新崽子.从数量上我们也可以看到 从第三个月开始,本月的兔子是前两个月兔子数量之和
  • 我们要求第n月有多少兔子=(n-1)+(n-2)= 前一个月的兔子加上前两个月的兔子总数

    private int rabbit(int month) { if (month <= 2){ //前两个月不能生兔子,所以返回只有一对兔子 return 1; }else { //之后就是公式:本月就等于前两个月兔子之和 return rabbit(month - 1) + rabbit(month - 2); } }
  • 如下示意图

markdown_img_paste_20181128174251964

折半查找

  • 折半查找是建立在数据有序的基础上的!!
  • 比如一组数据:1,5,19,21,26,33,56,77,89,110
  • 折半查找依靠三个指针

markdown_img_paste_2018112818312668

  • 如上,该开始,第一个指针指向起始下标的数据,第二个指针指向的是数据中间位置的数据,第三个指针指向的是数据结束的位置的数据
  • 那么他是怎么进行查找的呢? 比如查找56
  • 首先需要判断,中间指针指向的数据的大小与56的关系,33<56,所以就将开始处的指针指向中间处的指针的位置 +1 ,然后中间处的指针再指向开始处索引到结束处指针之间的中间位置,就像这样

markdown_img_paste_20181128194039730

  • 然后在判断中间指针上的数据与55的关系,77>56,这时候,就将结束处的指针指向中间指针的位置,然后将中间的指针在指向开始处索引到结束处指针之间的中间位置,就比如这样

markdown_img_paste_20181128194221774

  • 然后再判断中间指针上的数据与56的关系,此时中间处的指针指向的数据已经等于56,即查找到了需要的数据
    -上面就是折半查找的原理,就是利用中间值与指定数字对比然后迅速的将一半的数据过滤掉,这也被称为二分查找,注意数据必须是有序的
  • 我们知道了原理,就用代码实现一下

    //循环实现 /** * @param nums 指定有序数据集 * @param n 需要查找的数据 */ void searchNum(int[] nums,int n){ //由于数据集是有序的,所以如果超过了数据集的最大值和最小值或者长度为0,直接返回 if (nums[0]>n || nums[nums.length -1] < n || nums.length == 0){ System.out.println("需要查找的数据不在指定数据范围内"); return; } int start = 0; //起始位置 int end = nums.length - 1; // 结束位置 int mid = end / 2; //中间位置 //折半查找正式开始 while (start <= end){ if (nums[mid] == n){ //如果是等于,那么就输出 System.out.println(mid + " -> " + nums[mid]); return; }else if (nums[mid] < n){ //代表中间值小于指定数的情况 start = mid + 1; // 将开始位置的指针赋值为中间索引 mid = (start+end) /2 ; //赋值中间索引为开始和结束索引中间位置 }else if (nums[mid] > n){ //代表中间值大于指定数的情况 end = mid - 1; mid = (start+end) /2 ; } } System.out.println("需要查找的数据不在指定数据范围内"); } //递归实现 /** * @param nums 指定有序数据集 * @param start 开始查找位置 * @param end 查找结束位置 * @param n 需要查找的数据 */ private void searchNum(int[] nums, int start, int end, int n) { //由于数据集是有序的,所以如果超过了数据集的最大值和最小值或者长度为0,直接返回 if (nums[start]>n || nums[end] < n || nums.length == 0){ System.out.println("需要查找的数据不在指定数据范围内"); return; } int mid = (start + end) / 2; if (nums[mid] == n ){ System.out.println(mid + " -> " + nums[mid]); return; }else if (nums[mid] < n){ searchNum(nums,mid + 1,end,n); }else if (nums[mid] > n){ searchNum(nums,start,mid - 1,n); } }

汉诺塔

  • 游戏规则,有X,Y,Z三个柱子,将X柱子上的方块全部移动到另外一个柱子上,而且每次移动,必须保证大块在小块上面
  • 看到这先放松一下,玩一下关于本题有关的游戏吧~:汉诺塔在线游戏:必须自己玩一下
  • 玩完之后,我们队汉诺塔应该是有个基本的认识了,这也是一道可以用递归来解决的问题,那么怎么解呢?
  • 比如我们拿三个块来举例子

markdown_img_paste_20181128204630861

  • 这是初始的状态,我们要在保证游戏规则的情况下,完成将一个柱子上的块移动到另一个柱子上,并保持块是从小到大的,那么移动的步骤就应该是

    • 为了让最大的块移动到Z,那么我们就必须将n-1=3个块借助Z移动到Z:n-1:X->Z->Y
    • 现在就X就剩下了一个最大块,我们就可以直接将它放入Z上:X->Z
    • 现在的情况就成了X为空柱子,Y上有前三个大小的块,而Z上只有最大的块,现在需要做的就是让Y借助X将三个块移动到Z上:n-1:Y->X->Z
  • 看到这有人肯定会有疑问,你这不说的就是废话嘛,那么请接着看

markdown_img_paste_20181128205128605

  • 上面这种情况,是不是就是上面中废话的第二步已经完成的状态,那么我们现在可以忽略那个绿色的最大块,忽略后是不是就成了Y上有三个块,然后移动到Z上?那么Y上的三个怎么移动到Z上呢?

    • 首先Y借助Z将前两个块移动到X上,然后Y上就剩下了一个第二大块:蓝色的:n-1-1:Y->Z->X
    • 然后将蓝色第二大块移动到Z上Y->Z
    • 然后现在就剩下了X上的两个块没有移动到Z上,那么你借助Y移动到Z不就行了嘛n-1-1:X->Y->Z ,如图,所以呢你现在是不是发现,如果忽略掉Z上已经移动上去的两个块,现在就剩下了把两个块移动到Z上的问题~~~!!!

markdown_img_paste_20181128205754181

  • 都说到这里了,那么X上的两个怎么移动呢?

    • 首先X将最小块移动到Y:X->Y
    • 然后X借助Y将剩下的一个块移动到Z:n-1-1-1:X->Y->Z
    • 到这就只剩下Y有一个最小块了,所以直接扔过去就好了,这也就显示了递归的出口:当块为1
  • 所以总结一下,汉诺塔问题就是借助一个柱子,将N-1个块移动到另一个柱子上,排除出来的那一个最大块,可以暂时忽略,因为现在任何一个块都可以放到最大块上,然后现在就剩一下了一个n-1个块的移动问题,重复再重复,当块为1的时候,就是递归要退出的出口了

    /** * @param n 汉诺塔的层数 * @param x 第一个柱子的名字 * @param y 第二个柱子的名字 * @param z 第三个柱子的名字 */ private void hanoi(int n, char x, char y, char z) { if (n == 1){ //如果块只剩下一个了,那么肯定是最小的块还没有移动,所有的块已经按顺序移动到了Z上, //所以剩下的就是将x 移动到 z System.out.println(x + "->" + z); }else { //一共n个块,首先必须将n-1个块从x借助z移动到y,然后现在的情况就是x剩下最大的块,y有n-1个块 //z为空柱子 hanoi(n - 1, x , z , y); //代表将x上剩下的最大的块移动到Z System.out.println(x + "->" + z); //现在的情况剩下的就是将y上的n-1个块借助x移动到z hanoi(n - 1, y , x , z); } }
  • 上面会输出移动的步骤,不妨再次打开游戏,按照步骤来,用最短的时间拿最高得分~
  • 到这我只能说是理解了汉诺塔问题并且知道了解决办法,不过看到递归能够这么简洁的解决此问题,真是超级无敌太神奇

八皇后

  • 皇后你就想成是武则天,位高权重,你正眼看他侧眼看他哪怕是斜着看他,只要被他发现,你就会掉脑袋,所以这就是八皇后问题,八皇后就是有八个武则天不能互相盯着,(即没有任何两个皇后在同一行、同一列或者同一对角线上),如下

markdown_img_paste_20181128215651521

  • 如上,他的同行和同列以及他对应的斜线都不允许有人挡路,在这个条件下,然后在这个八成八的方格里放入八位皇后,请问有几种摆放方法?

漫画描述八皇后问题

  • 首先我们先不考虑有多少种算法,我们先把其中一种方案求出来
  • 我们首先需要做的就是模拟一个棋盘出来,我们用一维数组,比如arrs[4]=3,代表了数组的第三行第四列,即:[3,4]=arrs[列]=行,数组下标为列值,数组索引位置数字代表行值
  • 比如我们需要模拟三个位置:[3,6],[2,1],[0,4],那么就可以转换成

    [3,6] = {arrs[6]=3} [2,1] = {arrs[1]=2} [0,4] = {arrs[4]=0}
  • 所以知道这样的存储数据方式后,如果我们八个皇后的位置是[0,1],[1,2],[2,3],[3,4],[4,5],[5,6],[6,7],[7,4],那么我们的int[8]数组里面的值就是int[] chess = {1,2,3,4,5,6,7,4},这样存放的好处是,利用数组下标加上对应位置上的数值,直接锁定皇后位置
  • 好了现在模拟棋盘位置的问题解决掉了,下面就是皇后的位置的确定问题,我们容易想到的就是逐列遍历,如果该位置允许放入皇后,那么我们就将此位置标记,并继续往下遍历寻找位置(递归入口),当一行中没有合适的皇后的落脚处的时候,我们需要返回上一行(回溯),将上一行的皇后移动到另一个新的位置,然后再继续往下遍历寻找,当我们的第八位皇后找到合适的位置的时候,这就代表了已经生成了一种八皇后问题的摆放方案,如下

1336311585_2632

  • 对解决办法有了基本的认识后,还有一个问题,那就是怎么确定该位置是可以落脚的,如图

markdown_img_paste_20181129151001783

  • 如何落脚也就是如何去判断他的周围禁区是否有其他皇后,为了方便,我又画了一张坐标图,现在我们来找找规律

markdown_img_paste_2018112915124563

  • 我们采用的是一列一列的放入皇后,即第一列安放完成后,寻找第二列合适的位置安放皇后,所以我们这种方法并不存在两个皇后在同一列上的问题,(因为不同列是由递归切换的),所以我们现在需要思考的是,皇后的同一行是否有皇后,或者皇后的斜方向是否有皇后,所以我们就只用找同行,或者斜方向的规律就好了
  • 同行:拿[4,1],[4,2]举例子,这两个是同一行的,那么我们怎么用数组表示的呢?:arr[1]=4和arr[2]=4,我们发现了在一行的数据的数组值是一样的,所以表示同一行就可以这样:arr[n]==arr[m],n和m代表两个不同列
  • 斜方向:我们拿[5,0],[6,1],[7,2]这一斜行数据距离,转换为数组为:arr[0]=5,arr[1]=6,arr[2]=7,我们发现了:数组之间下标之差的绝对值等于两个数组代表的数据的差的绝对值,,即可以表示:Math.abs(arr[n]-arr[m] == (Math.abs(n-m)))
  • 好了到这我们把棋盘,皇后位置如何表示,皇后如何判断周围有没有其他人这些问题都讲了一遍,下面就是代码时间

    public class MyQueen { //代表你在第几行上放置了皇后,下标为列,所以就构成了皇后的坐标[下标,值] = [列,行] private static int[] chess = new int[8]; /** * 设置皇后的核心方法 * @param col 从第几列开始设置 */ static void setQueen(int col){ // System.out.println("**********************"); boolean danger; //代表皇后试探的这个位置是否可以落脚 //如果到8了,那么就说嘛八个皇后已经安排好了 if (8 == col){ //打印棋盘 printChess(); //如果只想要一个方案,那么把return注释掉,打开System.exit(0)即可 return; // System.exit(0); } //一列上八个位置,所以循环八次,皇后需要逐个试探 for (int i = 0; i < 8; i++) { //每次将皇后放入每一列的第一个位置即[col,i] chess[col] = i; // System.out.println("皇后试探位置:["+i+","+col+"]"); danger = true; //chess中保存了已经安排好的皇后,既然遍历到col个了,那么肯定是col-1个皇后已经安排好了 for (int j = 0; j < col; j++) { //判断同行是否有皇后,此条件文章中已经推导出来 if (chess[j] == chess[col]){ // System.out.println("皇后比较行==位置"+"["+chess[j]+","+j+"] <-> "+"["+chess[col]+","+col+"]"); //有的话就赋值false danger = false; //如果此行有别人了,那么就没必须再往下判断了 break; //判断斜行是否有皇后,此条件文章中已经推导出来 }else if (Math.abs(chess[j] - chess[col]) == (col - j)){ // System.out.println("皇后比较行Math位置"+"["+chess[j]+","+j+"] <-> "+"["+chess[col]+","+col+"]"); //同上 danger = false; //同上 break; } } if (danger){ //danger赋值false,也隐含着皇后位置不合适,需要重新选择,所以不会进入这 //如果是true,那么就是安排舒服了,然后继续往下一列找寻下一个皇后的位置 setQueen(col +1); } //如果到这还都是false即没执行下一列的递归,那么就表示了这一列是没有满足条件的位置的,所以也隐含着此方法出栈,再次执行栈顶方法 //到达栈顶也就是上一列从新开始寻找位置 } } //打印棋盘 private static void printChess() { for (int i = 0; i < 8; i++) { System.out.print(chess[i]); } System.out.println(); } public static void main(String[] args) { setQueen(0); } }
  • 可以运行一下代码,将输出调整为只要一个结果,然后打开System.out...注释,然后拿着表格对着控制台信息,走一下,就能明白个大概了
  • 此算法有好多种,网络上也有很多,自己对皇后问题还是有点蒙,可能是因为递归还是不熟吧,如果本篇文章有什么错误的地方恳请指正,谢谢
原文链接:https://yq.aliyun.com/articles/673980
关注公众号

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。

持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。

文章评论

共有0条评论来说两句吧...

文章二维码

扫描即可查看该文章

点击排行

推荐阅读

最新文章