深入了解递归思想

╰+攻爆jí腚メ 2022-05-18 08:20 351阅读 0赞

递归(Recursion),指在函数的定义中使用函数自身的方法,即程序的自身调用.

递归通常用来解决结构自相似的问题.所谓结构自相似,是指构成原问题的子问题与原问题在结构上相似,可以用类似的方法解决.具体的,整个问题的解决,可以分为两部分:第一部分是一些特殊情况,有直接的解法;第二部分与原问题相似,但比原问题的规模要小.实际上,递归是把一个不能或不好解决的大问题转化为一个或几个小问题,再把这些小问题进一步分解成更小的问题.直至每个小问题都可以直接解决.因此,递归有两个基本要素:即边界和递归模式.

递归模式:大问题是如何分解为小问题,也成为递归体.递归函数只有具备了这两个要素,才能在有限次计算后得出结果.

理解为:

在递归函数中,调用函数和被调用函数是同一个函数,需要注意的是递归函数的调用层次,如果把调用递归函数的主函数成为第0层,进入函数后,首次递归调用自身成为第1层调用;从第i层递归调用自身称为第i+1层.反之,退出第i+1层调用应该返回第i层.

函数的内部执行过程:

一个递归函数的调用过程类似于多个函数的嵌套的调用,只不过调用函数和被调用函数是同一个函数.为了保证递归函数的正确执行,系统需设立一个工作栈.具体的说,递归调用的内部执行流程如下:

  1. 运行开始时,首先为递归调用建立一个工作栈,其结构包括值参.局部变量和返回地址.
  2. 每次执行递归调用之前,把递归函数的值参和局部变量的当前值以及调用后的返回地址压栈;
  3. 每次递归调用结束后,将栈顶元素出栈,使相应的值参和局部变量恢复为调用前的值,然后转向返回地址指定的位置进行

在使用递归前,要有一种化归思想..

化归思想:将一个问题由难化易,由繁化简,由复杂化简单的过程称为化归,他是转化和归结的简称

特点:

  1. 自己调用自己

  2. 要有结束的条件

    • 递归就是方法里自身调用自身
    • 入口:递归一定要有入口函数
    • 出口:递归一定要有出口,在使用递归策略时,必须有一个明确的递归结束条件,成为递归出口.
    • 效率:递归算法解题通常显得很简洁,但递归算法解题的运行效率较低.所以一般不提倡用递归算法设计程序.使用的调用层数最高不要超过10级.
    • 栈溢出:在递归调用的过程当中系统为每一层的返回点.局部量等开辟了栈来存储.递归次数过多容易导致栈溢出.

基本步骤:

  1. 初始化算法.递归程序通常需要一个开始时使用的种子值(seed value).要完成此任务,可以向函数传递参数,或者提供一个入口函数,这个函数是非递归的,但可以为递归计算设置种子值.
  2. 检查要处理的当前值是否已经与基线条件相匹配.如果匹配,并进行处理并返回值.
  3. 使用更小的或更简单的子问题(或多个子问题)来重新定义答案
  4. 对子问题运行算法
  5. 将结果合并入答案的表达式
  6. 返回结果.,

总结:初始化——>检查当前值与基线条件的匹配——>化小量定义——>对子问题运行算法——>结果归总——>返回结果

简单的一个递归方法:

  1. /**
  2.      * @Author Young
  3.      * @Description  阶乘算法
  4.      * @Date 10:36 2018/8/1
  5.      * @Param 
  6.      * @return
  7.      * 10*9*8*7*6*5*4*3*2*1
  8.      *      n*(n-1)*(n-2)
  9.      **/
  10.     public static Double diGui(int n){
  11.         if(n <= 1 ) return 1D;
  12.             return n*diGui(n-1);
  13.     }

以阶乘为例简要理解一下,递归的深层次含义:

递归就是某个函数直接或间接的调用了本身,这种调用方式叫作递归调用.说白了,还是函数调用.既然是函数调用,那么就要遵循一个原则:所有被调用的函数都将创建一个副本,各自为调用者服务,而不受其他函数的影响.

对于函数fun()递归多少次,就有多少个副本,再利用内存的栈式管理,反向退出.栈的原理是压栈式的,先进后出.

对于递归函数,一旦被调用,函数将会在内存中复制出一份代码,再被调用就再复制一份.换句话说,可以把同一个函数的多次调用理解称为多个不同函数的一个调用,这样也会简单些..

再说 = 1 和 =0 时为什么退出.递归,很需要注意的就是死递归,也就是说,某一个函数进入了无限调用自身的情况,永无止境的消耗内存等资源,这在编程方面是一大忌.但凡是递归的函数,一定会在某个地方存在能够返回上一层函数的代码,否则必定死递归.fun()函数中.那个else就是返回的出口,可以这样想,如果没有那个if来进行判断,递归到什么时候算完?fun()会一直调用自己.别调用的函数不会自动结束,因为一旦某个函数A中调用了函数B(或者自己),那么A中的代码会停在调用的为知,而转向B中取执行,同理,如果B又调用了函数C,那么B又停在调用的位置,去执行C,如果无限调用,那么程序是永远不会结束的.当然也有一种可能,A调用B,然后继续执行自己的代码,不管B的死活,这种就属于多线程的范畴.我们对递归来讲的是单线程.

当n=3时,即3!的值

  1. 一层执行到fun=digui(3-1)*3;停止,执行二层fun=digui(3-1),也就是digui(2);
  2. 二层执行到fun=digui(2-1)*2;停止,执行三层digui(2-1),也就是digui(1);
  3. 三层执行到if(n<=1)return n;然后return n到二层的digui(2-1)的位置,二层继续执行;
  4. 二层执行到fun=1*2.然后就return()到digui(3-1)的位置,一层继续
  5. 一层执行fun=2*3,然后就return到了最初调用fun(3)的方法调用中,所以就得到y=6;

其实每一层都相当于一个不同的函数,可以给他们的函数名称不同.只要注意一点,调用一次,不是在代码本身上执行,而是会复制出一份再执行,是另外一个压栈的动作.

尾递归解决栈溢出问题

栈溢出:使用递归函数需要注意防止栈溢出.在计算机中,函数调用是通过栈(stack)这种数据结构实现的,每当进入一个函数调用,栈就会加一层栈帧,每当函数返回,栈就会减一层栈帧.由于栈的大小不是无限的,所以,递归调用的次数过多,会导致栈溢出.

尾递归(tail-call)优化:在尾部进行函数调用时使用下一个栈结构覆盖当前栈结构,同时保持原来的返回地址.

本质是对栈进行处理,删除活动记录(activation record),在函数返回的时候,调用自身本身,并且return语句不能包含表达式.这样,编译器或者解释器就可以把尾递归做优化,使递归本身无论调用多少次,都只占用一个栈帧,不会出现栈溢出的情况.

要使调用成为真正的尾部调用,在尾部调用函数前,对其结果不能执行任何其他操作.

不管递归有多深,栈大小保持不变,尾递归属于线性递归的子集.用尾递归优化改造上面的阶乘算法,主要是要把每一步的乘积传入到递归函数中:

  1. /**
  2.      * @Author Young
  3.      * @Description //使用尾递归就行阶乘计算
  4.      * @Date 11:32 2018/8/1
  5.      * @Param
  6.      * @return
  7.      **/
  8.     public static Double pass(int n){
  9.         return recursion(n,1d);
  10.     }
  11.     public static Double recursion(int n,Double product){
  12.         if (n<=1) return product;
  13.         return  recursion(n-1,n*product);
  14.     }

从使用递归可以看到 return recursion(n-1,n*product)仅返回函数本身,n-1 和 n*product在函数调用前就会被计算,不影响函数调用.可以看到.

尾递归事实上和循环是等价的,没有循环语句的编程语言只能通过尾递归实现循环

添加两个常用的递归案例:

  1. /**
  2.      * @Author Young
  3.      * @Description 给一个数组a[]:a[0],a[1],...,a[n-1]如何用递归的方式求和？
  4.      * @Date 14:19 2018/8/1
  5.      * @Param
  6.      * @return
  7.      * 遍历数组.得到很多值
  8.      *  a[0]+fun(int[],1,length-1)=a[0]+a[1]+fun(int[],2,length-1)=...=a[0]+a[1]+...+a[length-1]
  9.      *  出口是 开始元素==结束元素时,输出a[a.length-1];
  10.      **/
  11.     public static int sumArr(int[] x,int start,int end){
  12.         if (start==end)return x[start];
  13.         return x[start]+sumArr(x,start+1,end);
  14.     }
  18. /**
  19.      * @Author Young
  20.      * @Description //求数组元素的最大值
  21.      * @Date 14:40 2018/8/1
  22.      * @Param
  23.      * @return
  24.      * 求3,2,6,7,2,4的最大值
  25.      *      赋值第一个元素为最大值,如果第二个大于第一个,就第二个的值赋值给最大值
  26.      *      出口是遍历结束
  27.      *
  28.      **/
  29.     public static int getMax(int[] a,int max,int begin,int end){
  30.         if (begin>end)return max;
  31.          max = max > a[begin] ? max : a[begin];
  32.          return getMax(a,max,begin+1,end);
  33.     }

.

发表评论

表情：
评论列表 （有 0 条评论，351人围观）

还没有评论，来说两句吧...

相关阅读