数据结构叶核亚递归幻灯片.ppt
数据结构叶核亚递归第1页，共36页，编辑于2022年，星期六递归算法递归算法 递归的概念递归的概念第2页，共36页，编辑于2022年，星期六一一 递归的概念递归的概念 若一个算法直接地或间接地调用自己本身，若一个算法直接地或间接地调用自己本身，则称这个算法是则称这个算法是递归算法递归算法。1.问题的定义是递归的问题的定义是递归的 例如：阶乘函数的定义例如：阶乘函数的定义 1 当当n=0时时 n!=n(n-1)1 当当n0时时第3页，共36页，编辑于2022年，星期六1 当当n=0时时 n!=n(n-1)!当当n0时时递归定义的函数形式为：递归定义的函数形式为：1 当当n=0时时 f(n)=nf(n-1)当当n1时时第4页，共36页，编辑于2022年，星期六 2、问题的解法存在自调用问题的解法存在自调用：例如：折半查找算法例如：折半查找算法第5页，共36页，编辑于2022年，星期六二二 递归算法的执行过程递归算法的执行过程例例1：阶乘的递归算法：阶乘的递归算法public static long fact(int n)throws Exceptionint x;long y;if(n high)return-1;/查找不成功查找不成功mid=(low+high)/2;if(x=amid)return mid;/查找成功查找成功else if(x amid)return bSearch(a,x,low,mid-1);/在上半区查找在上半区查找elsereturn bSearch(a,x,mid+1,high);/在下半区查找在下半区查找第8页，共36页，编辑于2022年，星期六测试主函数设计如下：测试主函数设计如下：public static void main(String args)int a=1,3,4,5,17,18,31,33;int x=17;int bn;bn=bSearch(a,x,0,7);if(bn=-1)System.out.println(x不在数组不在数组a中中);elseSystem.out.println(x在数组在数组a中，下标为中，下标为+bn);第9页，共36页，编辑于2022年，星期六递归调用执行过程：递归调用执行过程：第10页，共36页，编辑于2022年，星期六递归调用执行过程：递归调用执行过程：第11页，共36页，编辑于2022年，星期六三三 递归过程和运行时栈递归过程和运行时栈一般函数调用要保留的信息：一般函数调用要保留的信息：1、返回地址、返回地址 2、本函数调用时与形参结合的实参值，、本函数调用时与形参结合的实参值，包括函数名和函数参数。包括函数名和函数参数。3、本函数的局部变量值。、本函数的局部变量值。递归调用也要保存以上信息，但有于递归的递归调用也要保存以上信息，但有于递归的自调特性，所以必须使用自调特性，所以必须使用“递归工作栈递归工作栈”第12页，共36页，编辑于2022年，星期六第13页，共36页，编辑于2022年，星期六四四 递归算法的设计方法递归算法的设计方法递归算法的基本思想：递归算法的基本思想：对于一个比较复杂的问题，把原问对于一个比较复杂的问题，把原问题分解成几个相对简单且类同的子问题分解成几个相对简单且类同的子问题，使原问题的解决变成对子问题的题，使原问题的解决变成对子问题的解决，而子问题的子问题最终是可以解决，而子问题的子问题最终是可以直接解的。直接解的。第14页，共36页，编辑于2022年，星期六递归算法设计的条件递归算法设计的条件问题具有某中某种可能借用的类同自身问题具有某中某种可能借用的类同自身的子问题描述的性质。的子问题描述的性质。相对于原问题来说，子问题将更加简单化。相对于原问题来说，子问题将更加简单化。某一有限步的子问题有直接解存在。某一有限步的子问题有直接解存在。第15页，共36页，编辑于2022年，星期六算法的设计将原问题的求解分解成对子问题的将原问题的求解分解成对子问题的求解。求解。设计递归出口，即求解本原问题。设计递归出口，即求解本原问题。第16页，共36页，编辑于2022年，星期六分析：求分析：求n阶乘问题可以转换为求阶乘问题可以转换为求n-1的阶乘，当的阶乘，当n=0时，时，问题可以直接求解。问题可以直接求解。Long Fact(int n)int x;long int y;if(n=0)return 1;x=n-1;y=Fact(x);return n*y;第17页，共36页，编辑于2022年，星期六第18页，共36页，编辑于2022年，星期六汉诺塔问题汉诺塔问题第19页，共36页，编辑于2022年，星期六void hanoi(int n,char x,char y,char z)/将塔座x上按直径由小到大且至上而下编号为1至n/的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。1 if(n=1)2 move(x,1,z);/将编号为的圆盘从x移到z3 else 4 hanoi(n-1,x,z,y);/将x上编号为至n-1的 /圆盘移到y,z作辅助塔5 move(x,n,z);/将编号为n的圆盘从x移到z6 hanoi(n-1,y,x,z);/将y上编号为至n-1的 /圆盘移到z,x作辅助塔7 8 例例3 汉诺塔问题汉诺塔问题第20页，共36页，编辑于2022年，星期六五五 递归算法效率分析递归算法效率分析汉诺塔问题的效率分析汉诺塔问题的效率分析 汉诺塔问题的由来汉诺塔问题的由来 汉诺塔问题的盘子个数与移动次数关系。汉诺塔问题的盘子个数与移动次数关系。n=1 A到到C 1次次 n=2 A到到B，A到到C，B到到C 3次次 时间复杂度为：时间复杂度为：第21页，共36页，编辑于2022年，星期六第22页，共36页，编辑于2022年，星期六递归算法的时间效率为：递归算法的时间效率为：递归算法可转换为非递归算法，即用循递归算法可转换为非递归算法，即用循环算法来代替，转换后其时间效率为：环算法来代替，转换后其时间效率为：第23页，共36页，编辑于2022年，星期六 以斐波那契数列递归函数的执行效率为以斐波那契数列递归函数的执行效率为例来讨论递归算法的执行效率问题。例来讨论递归算法的执行效率问题。斐波那契数列斐波那契数列Fib(n)的递推定义是：的递推定义是：第24页，共36页，编辑于2022年，星期六按照上式，求第按照上式，求第n项斐波那契数列的递项斐波那契数列的递归函数如下：归函数如下：public static long fib(int n)if(n=0|n=1)return n;/递归出口递归出口else return fib(n-1)+fib(n-2);/递归调用递归调用第25页，共36页，编辑于2022年，星期六fib(5)的递归调用树的递归调用树第26页，共36页，编辑于2022年，星期六递归算法的时间效率为：递归算法的时间效率为：递归算法可转换为非递归算法，即用循递归算法可转换为非递归算法，即用循环算法来代替，转换后其时间效率为：环算法来代替，转换后其时间效率为：第27页，共36页，编辑于2022年，星期六六六 递归算法到非递归算法的转换递归算法到非递归算法的转换 一般来说，如下两种情况的递归算法可转化为一般来说，如下两种情况的递归算法可转化为非递归算法：非递归算法：（1）存在不借助堆栈的循环结构的非递归算法，）存在不借助堆栈的循环结构的非递归算法，如阶乘计算问题、斐波那契数列的计算问题、如阶乘计算问题、斐波那契数列的计算问题、折半查找问题等折半查找问题等（2）存在借助堆栈的循环结构的非递归算法。）存在借助堆栈的循环结构的非递归算法。所有递归算法都可以借助堆栈转换成循环结构所有递归算法都可以借助堆栈转换成循环结构的非递归算法。的非递归算法。第28页，共36页，编辑于2022年，星期六七七 设计举例设计举例一般递归函数设计举例一般递归函数设计举例 例例5：设计一个输出如下形式数值的递归函设计一个输出如下形式数值的递归函数。数。n n n .n.3 3 3 2 21第29页，共36页，编辑于2022年，星期六递归函数设计如下递归函数设计如下：public static void display(int n)for(int i=1;i 0)display(n-1);/递归递归 /n=0为递归出口，递归出口为空语句为递归出口，递归出口为空语句 第30页，共36页，编辑于2022年，星期六2 回溯法及设计举例回溯法及设计举例回溯法回溯法的基本思想是：的基本思想是：对一个包括有很多结点，每个结点有对一个包括有很多结点，每个结点有若干个搜索分支的问题，把原问题分解为若干个搜索分支的问题，把原问题分解为对若干个子问题求解的算法。对若干个子问题求解的算法。第31页，共36页，编辑于2022年，星期六当搜索到某个结点、发现无法再继续搜索下当搜索到某个结点、发现无法再继续搜索下去时，就让搜索过程回溯（即退回）到该结去时，就让搜索过程回溯（即退回）到该结点的前一结点，继续搜索这个结点的其他尚点的前一结点，继续搜索这个结点的其他尚未搜索过的分支；如果发现这个结点也无法未搜索过的分支；如果发现这个结点也无法再继续搜索下去时，就让搜索过程回溯到这再继续搜索下去时，就让搜索过程回溯到这个结点的前一结点继续这样的搜索过程；这个结点的前一结点继续这样的搜索过程；这样的搜索过程一直进行到搜索到问题的解或样的搜索过程一直进行到搜索到问题的解或搜索完了全部可搜索分支没有解存在为止。搜索完了全部可搜索分支没有解存在为止。第32页，共36页，编辑于2022年，星期六例例6：求解迷宫问题：求解迷宫问题第33页，共36页，编辑于2022年，星期六迷宫问题的搜索过程：第34页，共36页，编辑于2022年，星期六第35页，共36页，编辑于2022年，星期六通常用的是“穷举求解穷举求解”的方法例四、例四、迷宫求解迷宫求解第36页，共36页，编辑于2022年，星期六
