数据结构（第六课时 递归）Data Structures胡学钢 张 晶计算.ppt

《数据结构（第六课时 递归）Data Structures胡学钢 张 晶计算.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构（第六章递归）DataStructures胡学钢张晶计算机与信息学院2009年2月1第六章递归（Recursive）6.1递归的定义6.2递归的内部实现原理6.3递归程序的阅读6.4递归程序的正确性证明6.5递归程序的模拟——转换为非递归2第六章递归6.1递归的定义(1)作为一种程序形式的递归：在函数的执行过程中调用自身。可能有两种形式：直接递归----在函数体内调用自身，间接递归----函数中调用其他函数，并由其他函数调用自身(2)更是作为一种程序设计（算法设计）的技术的递归。因为一些问题的求解具有这样的特点：原问

2、题可以分解为若干子问题分别进行求解，适当地合并子问题的解可以得到原问题的解。而子问题的求解方式与原问题的求解相同，因而需要调用相同的函数来实现，由此而涉及到递归技术。36.1递归的定义例6.1阶乘n!的定义如下：1当n=0时n!=n(n-1)!当n>0时对应的求阶乘的递归函数如下：intfact（intn）{if(n==0)return1;elsereturnn*fact(n–1);}函数fact的函数体内调用自身，即fact(n–1);46.1递归的定义例6.2下面是一个递归函数fn的定义----斐波诺契函数：f1=1f2

3、=2fn=fn-1+fn-2n>2例6.3下面是一个对链表执行操作的函数，请判断其功能。voidprint(node*L){if(L!=NULL){cout<data;print(L->next);}}56.1递归的定义递归函数的一般形式：voidPname(参数表){if(条件)简单操作;else{简单操作;Pname(实参表);简单操作;[Pname(实参表);简单操作;]}}递归出口可能有多次的调用例如：在阶乘函数intfact（intn）{if(n==0)return1;elsereturnn*fact(n–

4、1);}递归出口是n==0函数也可以是其他类型；调用方式自然也不同66.2递归的内部实现原理6.2.1一般函数的内部实现程序A:…a1;B;a2;B;a3;B;a4;…程序A’:…a1;B;a2;B;a3;B;a4;…子程序BCallBCallBCallB76.2递归的内部实现原理（1）从程序的执行过程来讨论:在执行调用时,计算机内部至少执行如下操作:（a）保存返回地址,也就是将返回地址入栈。（b）为被调子程序准备数据:计算实在参数的值,并赋给对应的形参。（c）转入子程序执行。在执行返回操作时,计算机内部至少执行如下操作:（

5、a）从栈顶取出返回地址，并出栈。（b）按返回地址返回。86.2递归的内部实现原理（2）关于局部变量的实现的讨论在执行调用时,内部操作如下:（a）保存返回地址入栈，同时在栈顶为被调函数的局部变量和形参开辟存储空间。（b）为被调子程序准备数据:计算实在参数的值,并赋给对应的形参（在栈顶）。（c）转入子程序执行。在执行返回操作时,计算机内部至少执行如下操作:（a）从栈顶取出返回地址，并出栈（同时撤消了被调函数的局部变量和形参）。（b）按返回地址返回。96.2递归的内部实现原理（3）关于返回值的实现的讨论返回操作的内部实现修改为如下

6、几项:（a）若函数需要返回值，将其值保存到回传变量中。（b）从栈顶取出返回地址，并退栈。（c）按返回地址返回。（d）在返回后自动执行以下操作：若函数需要返回值，从回传变量中取出所保存的值，并传送到相应的变量或位置上。106.2递归的内部实现原理6.2.2递归调用的内部实现原理可将递归调用理解为:调用与自己有相同的代码和同名的局部变量的子程序。由此可知：执行递归调用及返回的内部实现与前述实现相同:在执行递归调用时,计算机内部执行如下操作:(a)开辟栈顶存储空间，用于保存：返回地址、被调层（函数）中的形参和局部变量的值。(b)为

7、被调层（函数）准备数据：计算实参的值,并赋给对应的形参（在栈顶元素中）。(c)转入子程序执行。116.2递归的内部实现原理在执行返回操作时,内部实现如下:（a）若函数需要返回值，将其值保存到回传变量中。（b）从栈顶取出返回地址，并退栈----同时撤消被调层子程序的局部变量及形参。（c）按返回地址返回。（d）在返回后自动执行如下操作：若函数需要返回值，从回传变量中取出所保存的值,并传送到相应的实变参或位置上。126.2递归的内部实现原理例：根据递归程序的内部实现过程求解returnhcf(28,6)的执行结果。inthcf(i

8、ntM,intN){(1)if(N==0)(2){cout<