计算机算法基础(第3递归算法.ppt

《计算机算法基础(第3递归算法.ppt》由会员分享，可在线阅读，更多相关《计算机算法基础(第3递归算法.ppt（52页珍藏版）》请在三一办公上搜索。

1、递归算法(Recursion),本章内容递归算法的实现机制递归化为非递归(难点)递归算法举例递归算法复杂性的计算(重点和难点),递归(Recursion)定义,直接或间接地调用自身的算法称为递归算法直接或间接调用自身的函数称为递归函数尾递归是指递归调用的语句在递归函数的最后一句递归算法的特点：用于解决一类递归定义的问题算法易于实现，简单明了,3.1 递归算法的实现机制,递归算法通过子程序/函数来实现子程序调用的形式参数传递和返回值的传送子程序调用的内部操作,1 子程序的调用形式,STACK,子程序/函数调用形式,关键：用栈保存返回地址用寄存器保存返回地址(某些嵌入式处理器),2 参数传递和返回

2、值的回传,参数传递按值的传送(值调用)按地址的传送(引用调用)两次值的传送地址的传送函数的返回值通过寄存器传递(AX/EAX)通过全局变量的传送例如 C+中的引用类型，一些脚本语言的引用变量类型都是按地址传送的例子,参数的传递,值参数(value parameter)用于输入参数的传递。一个值参数相当于一个局部变量，只是它的初始值来自为该形参传递的实参。对值参数的修改不影响为该形参传递的实参。引用参数(reference parameter)用于输入和输出参数传递。引用参数与实参变量表示同一存储位置，对值参数的修改直接影响为该形参传递的实参。,函数参数和函数的值,1 函数间的按值传递,在定义函

3、数时函数名后面括弧中的变量名称为“形式参数”(简称“形参”)，在主函数中调用一个函数时，函数名后面括弧中的参数(或表达式)称为“实际参数”(简称“实参”)。return后面的括弧中的值 称为函数返回值,例1调用函数时的数值传递,#include“iostream.h”void main()int x=5,y=10;swap(x,y);coutx“t”yendl;,例 交换函数 void swap(int a,int b)int temp;temp=a;a=b;b=temp;,运行结果：510,main函数在调用swap函数形式参数为a和b，实际参数为x和y，各自有不同的内存单元a和b交换时，并

4、不能影响x和y的值。这是按值传递的特性,2 函数间的地址传递,#include“iostream.h”void main()int x=5,y=10;swap(,例 交换函数 void swap(int*a,int*b)int temp;temp=*a;*a=*b;*b=temp;,运行结果：105,main函数在调用swap函数时，参数加了取地址运算符&，表示变量x和y的内存地址。形式参数为*a和*b，表示a和b是指针变量，*a和*b分别是指针a和b的内容。,3 函数间的引用传递,#include“iostream.h”void main()int x=5,y=10;swap(x,y);co

5、utx“t”yendl;,例 交换函数 void swap(int,运行结果：105,形式参数为&a和&b，即引用形式参数对引用形式参数的操作即对实际参数本身的操作,3子程序调用的内部操作,Caller:(主调函数)在栈顶为形式参数开辟空间计算实参值并赋给栈顶的形参返回地址入栈指令流转向被调函数的入口Callee:(被调函数)初始化：局部量保存在堆栈中从堆栈中取出形参运算返回：将返回值保存到回传变量中从栈中取出返回地址指令流转到返回地址处继续执行程序,递归程序的内部实现,内部实现和函数调用类似，代码只有一份优点：简单明了结构清晰，可读性强容易用数学归纳法来证明算法的正确性缺点：运行效率较低入/

6、出栈次数多，影响计算时间对系统栈的空间占用大，递归层次多时，容易导致栈溢出同一个函数多次的重复调用，开销大,3.2 递归化为非递归,直接递归化为非递归(迭代)原则：在过程的开始部分，初始化用户栈(替代系统栈)，增加一个全局变量retvalue用于保存返回值建立标号：分别在过程的第一条可执行语句处、每个递归调用处建立标号，依次为：L0,L1,L2,，做为入口地址和返回地址消去递归调用：局部变量、形参、返回地址入栈,形式参数赋值，goto语句到L0修改函数的返回部分：用户栈为空，返回返回值保存到全局变量中，同时将引用参数赋给栈顶的相应变量取出返回地址，恢复现场。(即恢复主调函数的局部量、参数等,注

7、意栈的平衡)转向返回地址处执行,int GCD(unsigned int a,unsigned int b)int res;if(a b)res=GCD(b,a);else if(b=0)res=a;elseres=GCD(b,a%b);return res;,a=b*r+q其中0=qb则：(a,b)=(b,q)=(D,0)D 为a,b的最大公因数,int GCD(unsigned int a,unsigned int b)CStack stack;int retvalue,retaddr;int res;L0:if(a b)res=GCD(b,a);L1:;else if(b=0)res=a

8、;elseres=GCD(b,a%b);L2:;return res;,建立用户栈设置临时变量-(返回值和返回地址)建立标号(入口地址和返回地址列表),int GCD(unsigned int a,unsigned int b)CStack stack;int retvalue,retaddr;int res;stack.push(a);stack.push(b);L0:b=stack.pop();a=stack.pop();/从堆栈取参数if(a b)res=GCD(b,a);L1:;else if(b=0)res=a;else res=GCD(b,a%b);L2:;return res;,

9、从堆栈中取参数,GCD例,参数的传递可以不用stack恢复现场后a,b不再使用，所以不用保护a,b标号L0,L1,L2中,栈里保存的不可能是L0,L1也可以去掉，于是栈里的返回地址总是L2,返回地址也可以不用保存参数res也不需要保存在栈里用户栈就可以取消,3.3 递归算法设计,可用递归解决的问题P问题P具有规模不同规模的问题P，具有相同性质；并且大规模的问题由小规模的问题构成小规模的问题是可解的关键：找到递归的递推关系找到结束递归的条件,递归求解的伪代码,procedure P(参数表)beginif 满足递归出口then 简单操作;elsebegin简单操作;CALL P;简单操作;end

10、;endendp,简单的0/1背包问题,设一个背包容纳的物品最大质量为m,现有n件物品，质量为m1,m2,mn,均为正整数。要求从中挑选若干件，使背包质量之和正好为m.（在此问题中，第i件物品要么取，要么不取，不能取一部分，故问题可能有解，可能无解）设用knap(m,n)来表示此问题。有解为true,否则为false,先考虑将物品mn放入背包的情况：knap(m,n)=若mn=m,则knap(m,n)true若mn m,则knap(m,n)knap(m,n-1)否则mn m，则knap(m,n)knap(m,n-1)knap(m-mn,n-1),bool knap(m,n)if(n=1)/出口

11、条件if(m1=m)return true;else return false;if(mn=m)return true;if(mn m)return knap(m,n-1);if(knap(m-mn,n-1)return true;return knap(m,n-1);,Hanoi塔问题,汉诺塔（Tower of Hanoi）游戏据说来源于布拉玛神庙。游戏的装置如图所示（图上以3个金片例），底座上有三根金的针，第一根针上放着从大到小64个金片。游戏的目标是把所有金片从第一根针移到第三根针上，第二根针作为中间过渡。每次只能移动一个金片，并且大的金片不能压在小的金片上面。该游戏的结束就标志着“世界

12、末日”的到来。,分析：,游戏中金片移动是一个很繁琐的过程。通过计算，对于64个金片至少需要移动 264 1=1.61019 次。,不妨用A表示被移动金片所在的针（源），C表示目的针，B表示过渡针。对于把n（n1）个金片从第一根针A上移到第三根针C的问题可以分解成如下步骤：,（1）将n-1个金片从A经过C移动到B。,（2）将第n个金片移动到C。,（3）再将n-1个金片从B经过A移动到C。,这样就把移动n个金片的问题转化为移动n-1个金片的问题，即移动n个金片的问题可用移动n-1个金片的问题递归描述，以此类推，可转化为移动一个金片的问题。显然，一个金片就可以直接移动。,void hanoi(int

13、 n,int a,int b,int c)if(n 1)hanoi(n-1,a,c,b);move(n,a,b);hanoi(n-1,b,a,c);else move(n,a,b);/结束条件,棋子移动,问题描述：有2n个棋子排成一行，白子用0代表，黑子用1代表。n=5的状态为：0000011111_ _(右边至少两个空位)移动规则：(1)每次必须移动相邻的两个棋子，这两个棋子不能互换位置(2)移动的颜色不限，移动的方向不限要求：最后成为 _ _ 0101010101 的状态(中间无空格)。,空格在任何地方都是可等价变换的问题规模为n和为n-1有相似的地方吗？000000111111_ _(问

14、题的规模n)0000011111_ _01(问题的规模 n-1,?)结论：(1)规模为n的问题可以通过两步的移动变成规模为n-1的问题!(2)初值（递归的结束条件n=?可以解）,1.初值的判断：n=2,0011_ _ 0_ _ 101 010_ _ 1,无解n=3,无解n=4:,0 0 0 0 1 1 1 1 _ _0 0 0 _ _ 1 1 1 0 10 0 0 1 0 1 1 _ _ 10 _ _ 1 0 1 1 0 0 10 1 0 1 0 1 _ _ 0 1_ _ 0 1 0 1 0 1 0 1,2.递推关系式:0 0 0.0 0 0 1 1 1.1 1 1 _ _(n)0 0 0.0

15、 0 _ _ 1 1.1 1 1 0 10 0 0.0 0 1 1 1 1.1 _ _ 0 1(n-1)对n-1个棋子进行递归的移动直到n=4为止,3.算法实现：(对棋子的位置进行编号，从1,2,2n,2n+1,2n+2)void chess(int n)/n为移动的棋子数，n4 if(n=4)/递归出口 else if(n4)/进入递归 move_to(n,n+1,2n+1,2n+2);move_to(2n-1,2n,n,n+1);chess(n-1);,4.思考：如果棋子的移动规则改为每次移动相邻的3个(4,5,)棋子，其他条件不变，则如何解决此问题？递归关系式的推导初值的判断(n=?有解

16、)算法的实现,n个元素的全排列,N=1,输出 1N=2,输出 1,2 2,1N=3,输出 1,2,3 1,3,2 2,1,3 2,3,1 3,1,2 3,2,1,解决：递推关系式初始值(递归的出口)算法实现,a=1,2.3,4,n;/对ak an 进行全排列void Range(a,k,n)if(k=n)Print(a);/输出排列 else for(i=k;in;i+)ak ai;/交换值 Range(a,k+1,n);/递归排列剩下的元素 ai ak;/交换值 初始调用：Range(a,0,n);,4.递归关系式的计算,递归算法时间复杂度的分析(重点)递归算法时间复杂度的计算(难点),4.

17、1递归算法时间复杂度分析,根据递归算法思想，可以得到递归算法的时间复杂度的递推关系式求解递推关系式即可例：GCD,T(a,b)=T(b,a%b)+C0,其中C0为常数最坏情况：T(a)=T(a/2)+C0=O(logn),例：一个楼有n个台阶，有一个人上楼有时一次跨一个台阶，有时跨2个台阶。问此人共有几种不同的上楼方法，并分析算法的时间复杂度。解：设H(n)为上楼的方法总数，则：当n=1,H(1)=1当n=2,H(2)=2当n2时,H(n)=H(n-1)+H(n-2)下面分析时间复杂度：设为T(n),T(n)2T(n-1)22T(n-2)2n-1T(1)=O(2n),4.2时间复杂度的计算-迭

18、代法,T(n)=2T(n/2)+cn=2(2T(n/4)+c*n/2)+cn=22T(n/4)+cn+cn=23T(n/23)+cn+cn+cn=2kT(n/2k)+cn+cn+cn=2k*0+kcn=cnlog2n=O(nlogn),K个,设 n/2k=1,则 k=log2n,求O(T(n)=?,recursion tree（递推树、迭代树）,汉诺塔（Tower of Hanoi）问题：假设move所需的时间为1，则其时间复杂度：,T(n)=2T(n-1)+1=2 2T(n-2)+1+1=22T(n-2)+2+1=23T(n-3)+22+2+1=2n-1T(1)+2n-2+23+22+2+1

19、=2n-1+2n-2+23+22+2+1=2n-1,若有64个圆盘，则需要移动264-1=1.61019次,T(n)=2T(n-1)+n=2 2T(n-2)+n-1+n=22T(n-2)+2(n-1)+n=23T(n-3)+22(n-2)+2(n-1)+n=2n-1T(1)+2n-2*2+23(n-3)+22(n-2)+2(n-1)+n=2n-1+2n-2*2+23(n-3)+22(n-2)+2(n-1)+n,求O(T(n)=?,T(n)=2n-1+2n-2+23+22+2+20+2n-2+23+22+2+20+22+2+20+2+20+20=(2n-1)+(2n-1-1)+(22-1)+(2-1)=2n+1-2 n=O(2n),思考题目,1.写出的递归求解算法，并改为非递归算法2.用c/c+程序实现最大公约数的递归和非递归算法,