深入了解递归思想

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

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

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

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

理解为:

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

函数的内部执行过程:

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

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

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

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

特点:

1.  ***自己调用自己***
2.  ***要有结束的条件***

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

基本步骤:

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

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

简单的一个递归方法:

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

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

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

对于函数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语句不能包含表达式.这样,编译器或者解释器就可以把尾递归做优化,使递归本身无论调用多少次,都只占用一个栈帧,不会出现栈溢出的情况.

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

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

/**
         * @Author Young
         * @Description //使用尾递归就行阶乘计算
         * @Date 11:32 2018/8/1
         * @Param
         * @return
         **/
        public static Double pass(int n){
            return recursion(n,1d);
        }
        public static Double recursion(int n,Double product){
            if (n<=1) return product;
            return  recursion(n-1,n*product);
        }

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

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

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

/**
         * @Author Young
         * @Description 给一个数组a[]:a[0],a[1],...,a[n-1]如何用递归的方式求和？
         * @Date 14:19 2018/8/1
         * @Param
         * @return
         * 遍历数组.得到很多值
         *  a[0]+fun(int[],1,length-1)=a[0]+a[1]+fun(int[],2,length-1)=...=a[0]+a[1]+...+a[length-1]
         *  出口是 开始元素==结束元素时,输出a[a.length-1];
         **/
        public static int sumArr(int[] x,int start,int end){
            if (start==end)return x[start];
            return x[start]+sumArr(x,start+1,end);
        }

/**
         * @Author Young
         * @Description //求数组元素的最大值
         * @Date 14:40 2018/8/1
         * @Param
         * @return
         * 求3,2,6,7,2,4的最大值
         *      赋值第一个元素为最大值,如果第二个大于第一个,就第二个的值赋值给最大值
         *      出口是遍历结束
         *
         **/
        public static int getMax(int[] a,int max,int begin,int end){
            if (begin>end)return max;
             max = max > a[begin] ? max : a[begin];
             return getMax(a,max,begin+1,end);
        }