第3章 递归算法.ppt

1、第三章递归算法、递归算法的概述、递归是强有力的设置方法递归算法的特征，递归算法的基本思想是将解决一个大问题转换成一些小问题，重复转换直到问题小直接可以解决，如果这些小问题大(1)递归条件；(1)递归的下一步骤比上一步骤简单；(2)在有限的步骤内完成；(3)需要递归的出口。 3.1递归算法的实现机制3.1.1子例程的内部实现原理1 .子例程调用的一般形式是：当主例程运行到Call A时，系统自动保存第一地址，在调用a结束时从系统获得门地址主程序有多次对同一程序a的调用。 在第I次子程序a的反复调用之前，系统自动保存地址I，在第I次调用a结束后能够顺利地对每个地址I进行闭锁。 此时，与一次调用不同

2、，应保存的地址为多个，但在某个时刻最多只有一个地址，一旦取得地址，就释放预约地址。 主程序、子程序a、呼叫a 13360呼叫a 2:n次调用、主程序、子程序a、子程序b、呼叫b 23360、呼叫a 13360、嵌套调用、主程序当主程序运行到Call A或Call B时，系统会自动保存地址1，并在第二次调用子程序Call B或Call A时保存地址2。 这两种情况都与前两种情况不同，可能会在某一时刻保存多个地址，然后释放保存的地址。 此处的返回地址通常以类似于堆栈的数据结构存储。 堆栈在过程调用中的作用：过程调用需要将实际的残奥仪表值传递给波形残奥仪表。 过程的门地址必须暂时存储在某个地方。 过

3、程中，必须分配局部变量2 .值的回复实际参加形残奥仪表的数据传输方式： 1、值传输(例如c语言的残奥仪表传输方式、PASCAL的值残奥仪表)调用前后的值残奥仪表对应的实际残奥仪表不变2、地址传输对应的实际残奥仪表的值在执行中变化的可变残奥仪表的返回值，有(1)2次的值传达方式的2种实现方式。 在指定类型的残奥仪表中设置适当的存储空间，在执行调用时将实际残奥仪表传递给残奥仪表，并在返回时将实际残奥仪表的值返回给实际残奥仪表。 (2)地址转发方式。 在内部对残奥仪表设定地址，在调用时首先执行地址传送，将实际残奥仪表的地址传送到残奥仪表，在子程序执行中，对残奥仪表的操作实际上是对对应的实际残奥仪表的

4、操作。 在后面的讨论中，对变量的值的回复使用第一方式，即二次值传送方式。 3 .子程序调用的内部操作(1)调用执行时系统执行的操作： a .转移到地址堆栈，并且在堆栈的最上方打开用于被调节程序的局部变量的空间b .准备用于被调节程序的数据：校正实际残奥仪表值(2)执行返回操作时，系统执行的操作： a .变更关残奥字表或函数时，将其值存储在返回变量中b .从堆栈上取出门地址c .在门地址中门的d .自变量或函数发生变化时，从回复变量中取出Procedure main() Procedure A(x1，x2) end A Procedure B(x3，x4) call A(e，f):endbcal

5、la() c、d、2、堆叠、3.1.2递归程序的内部实现原理递归呼叫需要注意的是，当递归调用自己时，程序控制跳到同一代码执行而不是复制自己的代码，这种代码共享方式在当前堆栈中对应的关残奥元和局部变量的数据是不同的。 实例1.3斐波那契序列： F0=F1=1 Fi=Fi-1 Fi-2 (i1)算法获得1.7斐波那契序列进程f (n )/并将其返回到第n位置(f (n-1 ) f (n-2 ) endifendf算法的效率： f(n-2 )，F(n-3 )，若存在多个重复校正算法的改进：保存辗转相除： b=0，则a和b的最大公因数等于a。 如果是b0，则a和b的最大公倍数等于除以b和b的偶数的最大

6、公倍数。 求出修正算法1.8最大公因数procedure GCD(a，b) /约束ab/IFB=0then return (a ) else return (gcd (b，amodb ) )。 例1.5用递归策略设定的检索算法知道要素x和要素表A(1:n )，判断x是否等于a的某要素的值。 修正算法1.9在A(1:n )中，如果在xproceduresearch(i)/a(1:n )中有元素A(k)=x，则返回其最初出现的下标k，否则返回0/。 return (I ) : else : return (search (I1) ) endcaseendsearch，3.2递归非递归、直接递归删除

7、规则：基本思路：将递归调用位置替换为等效的非递归代码的13条规则初始化是过程的第一部分，通过插入描述为堆栈的代码初始化为空。 堆栈类型堆栈1. size top 0通常用于存储堆残奥计量器、局部变量、函数值和每次递归调用的门地址。 并将第一个可执行语句加上符号L1。 L1:第一个可执行语句由一系列指令替换，每次递归调用都执行以下规则： 以处理递归调用语句并将所有残奥元和局部变量的值存储在堆栈中。 top-top 1堆栈- top堆栈指针可看作全过程变量。 制作第I个新的标签Li，将标签的下标I存储在堆栈中.该标签的I值用于返回地址的修正运算. top top 1堆栈top I此标签放置在规则描

8、述的段中。 然后保存现场，修正此次调用的各实际残奥仪表(可能是公式)的值，将这些值分配给对应的形式残奥仪表。 无条件地插入导向语句的导向过程的开始部分： goto L1(完成上次的递归调用)，如果结束点的处理是函数，则在递归过程中如下处理包含此次的函数调用的语句：将该语句的此次的函数调用部分从堆栈的上面进行该函数调用如果此过程不是函数，则将在中创建的标签附加到生成的过渡语句后面的语句。 中的组合图层性质变更选项。 以下是过程中出现return语句时的处理。 注：纯进程结束时的end可以视为没有关联值的return语句，并且对于每个具有return语句的位置，如果堆栈为空，则执行正常回复的规则。

9、 如果不是if top 0 then return ()，则将所有输出残奥仪表(具有门限值的出口残奥仪表，out/inout类型)的当前值指定给堆栈顶部的相应变量。 如果堆栈有返回地址标签的下标，则Stackn插入该下标从堆栈退出的代码，将该下标分配给未使用的变量。 addrstacktoptop-1从堆栈中退出所有局部变量和残奥参数的值，并将其分配给相应的变量。中的组合图层性质变更选项。 如果此过程是一个函数，请修正return之后的表达式，并插入将结果值放置在堆栈顶部的命令。 Top Top 1 StackTop形式的值通过回复地址标签的添加来实现向该标签的转向。 if addr i then goto Li，例如1.6递归调用示例求数组元素中的最大值算法1.10求数组元素的最大值(递归算法)寻找procedure MAX1(i) /数组a中的最大值元素，并返回该元素的最大下标。/全球整数，A(1:n )，j，肯特里夫ia (j )特恩基尔斯基尔斯基尼夫雷特urn (