数据结构叶核亚递归课件.ppt

1、递归算法递归算法 递归的概念递归的概念一一 递归的概念递归的概念 若一个算法直接地或间接地调用自己本身，若一个算法直接地或间接地调用自己本身，则称这个算法是则称这个算法是递归算法递归算法。1.问题的定义是递归的问题的定义是递归的 例如：阶乘函数的定义例如：阶乘函数的定义 1 当当n=0时时 n!=n(n-1)1 当当n0时时1 当当n=0时时 n!=n(n-1)!当当n0时时递归定义的函数形式为：递归定义的函数形式为：1 当当n=0时时 f(n)=nf(n-1)当当n1时时 2、问题的解法存在自调用问题的解法存在自调用：例如：折半查找算法例如：折半查找算法二二 递归算法的执行过程递归算法的执行

2、过程例例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);/在下半区查找在下半区查找测试主函数设计如下：测试主函数设计如下：public static voi

3、d 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);递归调用执行过程：递归调用执行过程：递归调用执行过程：递归调用执行过程：三三 递归过程和运行时栈递归过程和运行时栈一般函数调用要保留的信息：一般函数调用要保留的信息：1、返回地址、返回地址 2、本函数调用时与形参结合的实参值，、本函数调用时与形参结合的实参值，包

4、括函数名和函数参数。包括函数名和函数参数。3、本函数的局部变量值。、本函数的局部变量值。递归调用也要保存以上信息，但有于递归的递归调用也要保存以上信息，但有于递归的自调特性，所以必须使用自调特性，所以必须使用“递归工作栈递归工作栈”四四 递归算法的设计方法递归算法的设计方法递归算法的基本思想：递归算法的基本思想：对于一个比较复杂的问题，把原对于一个比较复杂的问题，把原问题分解成几个相对简单且类同的问题分解成几个相对简单且类同的子问题，使原问题的解决变成对子子问题，使原问题的解决变成对子问题的解决，而子问题的子问题最问题的解决，而子问题的子问题最终是可以直接解的。终是可以直接解的。递归算法设计的

5、条件递归算法设计的条件 问题具有某中某种可能借用的类同自问题具有某中某种可能借用的类同自身的子问题描述的性质。身的子问题描述的性质。相对于原问题来说，子问题将更加简相对于原问题来说，子问题将更加简单化。单化。某一有限步的子问题有直接解存在。某一有限步的子问题有直接解存在。算法的设计 将原问题的求解分解成对子问题将原问题的求解分解成对子问题的求解。的求解。设计递归出口，即求解本原问题。设计递归出口，即求解本原问题。分析：求分析：求n阶乘问题可以转换为求阶乘问题可以转换为求n-1的阶乘，当的阶乘，当n=0时，问题可以直接求解。时，问题可以直接求解。Long Fact(int n)int x;lon

6、g int y;if(n=0)return 1;x=n-1;y=Fact(x);return n*y;)!1(*1!nnn汉诺塔问题汉诺塔问题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上编号为至

7、n-1的 /圆盘移到z,x作辅助塔7 8 例例3 汉诺塔问题汉诺塔问题五五 递归算法效率分析递归算法效率分析汉诺塔问题的效率分析汉诺塔问题的效率分析 汉诺塔问题的由来汉诺塔问题的由来 汉诺塔问题的盘子个数与移动次数关系。汉诺塔问题的盘子个数与移动次数关系。n=1 A到到C 1次次 n=2 A到到B，A到到C，B到到C 3次次 时间复杂度为：时间复杂度为：nnnnh222.22)(0121)2(nO 递归算法的时间效率为：递归算法的时间效率为：递归算法可转换为非递归算法，即用递归算法可转换为非递归算法，即用循环算法来代替，转换后其时间效率循环算法来代替，转换后其时间效率为：为：)2(nO)(nO

8、 以斐波那契数列递归函数的执行效率为以斐波那契数列递归函数的执行效率为例来讨论递归算法的执行效率问题。例来讨论递归算法的执行效率问题。斐波那契数列斐波那契数列Fib(n)的递推定义是：的递推定义是：时当时当时当1)2()1(1100)(nnFibnFibnnnFib按照上式，求第按照上式，求第n项斐波那契数列的项斐波那契数列的递归函数如下：递归函数如下：public static long fib(int n)if(n=0|n=1)return n;/递归出口递归出口else return fib(n-1)+fib(n-2);/递归调用递归调用 fib(5)的递归调用树的递归调用树Fib(5)

9、Fib(4)Fib(3)Fib(2)Fib(2)Fib(1)Fib(1)Fib(0)Fib(3)Fib(2)Fib(1)Fib(1)Fib(0)Fib(1)Fib(0)递归算法的时间效率为：递归算法的时间效率为：递归算法可转换为非递归算法，即用递归算法可转换为非递归算法，即用循环算法来代替，转换后其时间效率循环算法来代替，转换后其时间效率为：为：)2(nO)(nO六六 递归算法到非递归算法的转换递归算法到非递归算法的转换 一般来说，如下两种情况的递归算法可转化为一般来说，如下两种情况的递归算法可转化为非递归算法：非递归算法：（1）存在不借助堆栈的循环结构的非递归算法，）存在不借助堆栈的循环结构

10、的非递归算法，如阶乘计算问题、斐波那契数列的计算问题、如阶乘计算问题、斐波那契数列的计算问题、折半查找问题等折半查找问题等（2）存在借助堆栈的循环结构的非递归算法。）存在借助堆栈的循环结构的非递归算法。所有递归算法都可以借助堆栈转换成循环结构所有递归算法都可以借助堆栈转换成循环结构的非递归算法。的非递归算法。七七 设计举例设计举例 一般递归函数设计举例一般递归函数设计举例 例例5：设计一个输出如下形式数值的递归函设计一个输出如下形式数值的递归函数。数。n n n .n.3 3 3 2 21递归函数设计如下递归函数设计如下：public static void display(int n)for

11、(int i=1;i 0)display(n-1);/递归递归 /n=0为递归出口，递归出口为空语为递归出口，递归出口为空语句句 2 回溯法及设计举例回溯法及设计举例回溯法回溯法的基本思想是：的基本思想是：对一个包括有很多结点，每个结点有对一个包括有很多结点，每个结点有若干个搜索分支的问题，把原问题分解若干个搜索分支的问题，把原问题分解为对若干个子问题求解的算法。为对若干个子问题求解的算法。当搜索到某个结点、发现无法再继续搜当搜索到某个结点、发现无法再继续搜索下去时，就让搜索过程回溯（即退回）索下去时，就让搜索过程回溯（即退回）到该结点的前一结点，继续搜索这个结到该结点的前一结点，继续搜索这个

12、结点的其他尚未搜索过的分支；如果发现点的其他尚未搜索过的分支；如果发现这个结点也无法再继续搜索下去时，就这个结点也无法再继续搜索下去时，就让搜索过程回溯到这个结点的前一结点让搜索过程回溯到这个结点的前一结点继续这样的搜索过程；这样的搜索过程继续这样的搜索过程；这样的搜索过程一直进行到搜索到问题的解或搜索完了一直进行到搜索到问题的解或搜索完了全部可搜索分支没有解存在为止。全部可搜索分支没有解存在为止。例例6：求解迷宫问题：求解迷宫问题迷宫问题的搜索过程：1234(死路)3(死路)25(死路)26向前向左向右回溯回溯向前回溯向右向左路口动作结果进入2进入3进入4进入3进入2进入5进入2进入6进入7通常用的是“穷举求解穷举求解”的方法#$#$#$#例四、例四、迷宫求解迷宫求解