合肥工业大学数据结构课件第六章 递归.ppt

第六章 递归 （Recursive） 6.1 递归的定义 6.2 递归的内部实现原理 6.3 递归程序的阅读 6.4 递归程序的正确性证明 6.5 递归程序的模拟——转换为非递归 第六章 递归 6.1 递归的定义 (1) 作为一种程序形式的递归： 在函数的执行过程中调用自身。 可能有两种形式： 直接递归----在函数体内调用自身， 间接递归----函数中调用其他函数，并由其他函数调用自身 (2) 更是作为一种程序设计（算法设计）的技术的递归。 因为一些问题的求解具有这样的特点： 原问题可以分解为若干子问题分别进行求解， 适当地合并子问题的解可以得到原问题的解。 而子问题的求解方式与原问题的求解相同， 因而需要调用相同的函数来实现， 由此而涉及到递归技术。 6.1 递归的定义 例6.1 阶乘n!的定义如下： 1 当n=0时 n!= n(n-1)! 当n0时 对应的求阶乘的递归函数如下： int fact（int n）{ if ( n == 0 ) return 1; else return n * fact( n – 1 ); } 6.1 递归的定义 例 6.2 下面是一个递归函数fn的定义----斐波诺契函数： f1=1 f2=2 fn = fn-1 + fn-2 n2 例6.3 下面是一个对链表执行操作的函数，请判断其功能。 void print( node * L ) { if ( L != NULL ) { cout L - data; print( L - next ); } } 6.1 递归的定义 递归函数的一般形式： void Pname( 参数表 ){ if ( 条件 ) 简单操作; else { 简单操作; Pname (实参表); 简单操作; [Pname (实参表); 简单操作;] } } 6.2 递归的内部实现原理 6.2.1 一般函数的内部实现 6.2 递归的内部实现原理 （1）从程序的执行过程来讨论: 在执行调用时, 计算机内部至少执行如下操作: （a） 保存返回地址, 也就是将返回地址入栈。 （b） 为被调子程序准备数据: 计算实在参数的值, 并赋给对应的形参。 （c） 转入子程序执行。 在执行返回操作时, 计算机内部至少执行如下操作: （a） 从栈顶取出返回地址，并出栈。 （b） 按返回地址返回。 6.2递归的内部实现原理 （2）关于局部变量的实现的讨论 在执行调用时, 内部操作如下: （a） 保存返回地址入栈， 同时在栈顶为被调函数的局部变量和形参开辟存储空间。 （b）为被调子程序准备数据: 计算实在参数的值, 并赋给对应的形参（在栈顶）。 （c） 转入子程序执行。 在执行返回操作时, 计算机内部至少执行如下操作: （a）从栈顶取出返回地址， 并出栈（同时撤消了被调函数的局部变量和形参）。 （b）按返回地址返回。 6.2递归的内部实现原理 （3）关于返回值的实现的讨论 返回操作的内