数据结构叶核亚递归

数据结构叶核亚递归第一页，共三十六页，2022年，8月28日递归算法递归的概念第二页，共三十六页，2022年，8月28日一递归的概念

若一个算法直接地或间接地调用自己本身，则称这个算法是递归算法。1.问题的定义是递归的例如：阶乘函数的定义1当n=0时n!=n×(n-1)×…×1当n>0时第三页，共三十六页，2022年，8月28日 1当n=0时n!=n×(n-1)!当n>0时递归定义的函数形式为： 1当n=0时f(n)=n×f(n-1)当n>1时第四页，共三十六页，2022年，8月28日2、问题的解法存在自调用：例如：折半查找算法第五页，共三十六页，2022年，8月28日二递归算法的执行过程例1：阶乘的递归算法publicstaticlongfact(intn)throwsException{ intx; longy; if(n<0){ thrownewException("参数错！"); } if(n==0)return1; else{ x=n-1; y=fact(x); returnn*y; }}第六页，共三十六页，2022年，8月28日

设计一个计算3！得主函数如下,用来说明递归算法的执行过程：

publicstaticvoidmain(String[]args){ longfn; try{ fn=fact(3); System.out.println("fn="+fn); } catch(Exceptione){ System.out.println(e.getMessage()); }}第七页，共三十六页，2022年，8月28日例2：折半查找递归算法publicstaticintbSearch(int[]a,intx,intlow,inthigh){ intmid; if(low>high)return-1;//查找不成功 mid=(low+high)/2; if(x==a[mid])returnmid; //查找成功 elseif(x<a[mid]) returnbSearch(a,x,low,mid-1); //在上半区查找 else returnbSearch(a,x,mid+1,high); //在下半区查找}第八页，共三十六页，2022年，8月28日测试主函数设计如下：publicstaticvoidmain(String[]args){ int[]a={1,3,4,5,17,18,31,33}; intx=17; intbn; bn=bSearch(a,x,0,7); if(bn==-1) System.out.println("x不在数组a中"); else System.out.println("x在数组a中，下标为"+bn); }第九页，共三十六页，2022年，8月28日递归调用执行过程：第十页，共三十六页，2022年，8月28日递归调用执行过程：第十一页，共三十六页，2022年，8月28日三递归过程和运行时栈一般函数调用要保留的信息：1、返回地址2、本函数调用时与形参结合的实参值，包括函数名和函数参数。3、本函数的局部变量值。递归调用也要保存以上信息，但有于递归的自调特性，所以必须使用“递归工作栈”第十二页，共三十六页，2022年，8月28日第十三页，共三十六页，2022年，8月28日四递归算法的设计方法递归算法的基本思想：对于一个比较复杂的问题，把原问题分解成几个相对简单且类同的子问题，使原问题的解决变成对子问题的解决，而子问题的子问题最终是可以直接解的。第十四页，共三十六页，2022年，8月28日递归算法设计的条件问题具有某中某种可能借用的类同自身的子问题描述的性质。相对于原问题来说，子问题将更加简单化。某一有限步的子问题有直接解存在。第十五页，共三十六页，2022年，8月28日算法的设计将原问题的求解分解成对子问题的求解。设计递归出口，即求解本原问题。第十六页，共三十六页，2022年，8月28日分析：求n阶乘问题可以转换为求n-1的阶乘，当n=0时，问题可以直接求解。LongFact(intn){intx;longinty;if(n==0)return1;x=n-1;y=Fact(x);returnn*y;}第十七页，共三十六页，2022年，8月28日第十八页，共三十六页，2022年，8月28日汉诺塔问题第十九页，共三十六页，2022年，8月28日voidhanoi(intn,charx,chary,charz){//将塔座x上按直径由小到大且至上而下编号为1至n//的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。1if(n==1)2move(x,1,z);//将编号为１的圆盘从x移到z3else{4hanoi(n-1,x,z,y);//将x上编号为１至n-1的//圆盘移到y,z作辅助塔5move(x,n,z);//将编号为n的圆盘从x移到z6hanoi(n-1,y,x,z);//将y上编号为１至n-1的//圆盘移到z,x作辅助塔7}8}例3汉诺塔问题第二十页，共三十六页，2022年，8月28日五递归算法效率分析汉诺塔问题的效率分析汉诺塔问题的由来汉诺塔问题的盘子个数与移动次数关系。n=1A到C1次n=2A到B，A到C，B到C3次时间复杂度为：第二十一页，共三十六页，2022年，8月28日第二十二页，共三十六页，2022年，8月28日递归算法的时间效率为：递归算法可转换为非递归算法，即用循环算法来代替，转换后其时间效率为：第二十三页，共三十六页，2022年，8月28日以斐波那契数列递归函数的执行效率为例来讨论递归算法的执行效率问题。斐波那契数列Fib(n)的递推定义是：第二十四页，共三十六页，2022年，8月28日按照上式，求第n项斐波那契数列的递归函数如下：

publicstaticlongfib(intn){ if(n==0||n==1)returnn; //递归出口 elsereturnfib(n-1)+fib(n-2);//递归调用}第二十五页，共三十六页，2022年，8月28日fib(5)的递归调用树第二十六页，共三十六页，2022年，8月28日递归算法的时间效率为：递归算法可转换为非递归算法，即用循环算法来代替，转换后其时间效率为：第二十七页，共三十六页，2022年，8月28日六递归算法到非递归算法的转换一般来说，如下两种情况的递归算法可转化为非递归算法：（1）存在不借助堆栈的循环结构的非递归算法，如阶乘计算问题、斐波那契数列的计算问题、折半查找问题等（2）存在借助堆栈的循环结构的非递归算法。所有递归算法都可以借助堆栈转换成循环结构的非递归算法。第二十八页，共三十六页，2022年，8月28日七设计举例一般递归函数设计举例例5：设计一个输出如下形式数值的递归函数。 nnn...n ...... 333 22 1第二十九页，共三十六页，2022年，8月28日递归函数设计如下：publicstaticvoiddisplay(intn){ for(inti=1;i<=n;i++){ System.out.print(""+n); } System.out.println();

if(n>0)display(n-1); //递归 //n<=0为递归出口，递归出口为空语句}第三十页，共三十六页，2022年，8月28日2回溯法及设计举例回溯法的基本思想是： 对一个包括有很多结点，每个结点有若干个搜索分支的问题，把原问题分解为对若干个子问题求解的算法。第三十一页，共三十六页，2022年，8月28日当搜索到某个结点、发现无法再继续搜索下去时，就让搜索过程回溯（即退回）到该结点的前一结点，继续搜索这个结点的其他尚未搜索过的分支；如果发现这个结点也无法再继续搜索下去时，就让搜索过程回溯到