数据结构第6章递归

《数据结构第6章递归》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章递归6.1递归的定义6.2基本递归过程6.3递归的效率栈和递归在程序设计中的应用是非常广泛的，如对于迷宫的求解、表达式的求解等都可以用栈来解决。典型的hanoi塔问题，树和图的遍历等都可以用递归来解决。递归算法的设计实际上就是对问题的抽象的过程，如果抽象到每个小问题都有相同特征时，那就形成了递归，递归算法简明易懂。6.1递归的定义什么是递归xn=x*x*…*x*x（n个x连乘）xn+1=xn*xS(n)=1+2+3+…+(n-1)+nS(n+1)=S(n)+(n+1)优点：直观、有效定义：如果一个对象部分地包含它自身，或者利用自己定义自己的方式来

2、定义或描述，则称这个对象是递归的；如果一个过程直接或间接地调用自己，则称这个过程是一个递归过程。直接调用自身的递归过程称为直接递归。调用另一个过程并最终导致调用原过程的递归过程称为间接递归组成：递归调用、递归终止条件5递归求解的过程：对于一个比较复杂的问题，若能将它分解成若干相对简单、且解法相同或类似的子问题，那么当这些子问题获解时，原问题就获得求解－－分治策略。子问题无需分解就可直接求解时，停止分解，直接求解该子问题－－递归结束条件。7求解阶乘函数的递归过程longFactorial(longn){if(n==0)return1;//递归终止条件el

3、sereturnn*Factorial(n-1);}//递归调用过程以下三种情况适于用递归求解问题：问题的定义是递归的问题所涉及的数据结构是递归的；问题的解法满足递归的性质。1、问题的定义是递归的阶乘函数、幂函数和斐波那契数列。[例]阶乘函数的定义用(n-1)!定义n!计算斐波那契数列的函数Fib(n)的定义求解斐波那契数列的递归算法longFib(longn){if(n<=1)returnn;elsereturnFib(n-1)+Fib(n-2);}2、问题所涉及的数据结构是递归的[例]　单链表head=NULL●head指向一个空结点的数据结构

4、是一个单链表。●head指向一个非空结点，该结点的指针域指向一个单链表，这样的数据结构是一个单链表。7245…head36∧二叉树：二叉树是数据元素的有穷集合，它或者为空集（空二叉树），或者由一个根元素和其下的两棵互不相交的二叉树（左子树和右子树）构成。3、问题的解法满足递归的性质例如，汉诺塔(TowerofHanoi)问题问题的提出：在19世纪末，布拉玛神庙(TempleofBramah)里的传教士玩着一种游戏，据说他们的游戏装置是由一块铜板上有三根金刚石针，针上放有64个直径大小不等的金盘组成的。游戏的目标是把左面针上的金盘移动到右面的针上，移动过

5、程中一次只能移动一个盘子，不允许大盘放在小盘上面，只能借助于中间的针。他们认为这种游戏的结束就意味着世界末日的到来。欧洲人把这种游戏叫做汉诺塔(TowerofHanoi)游戏。6.2基本递归过程递归过程在实现时，发生递归调用：分为内部调用和外部调用。函数调用与过程调用递归调用正确进行：调用时参数传递正确过程结束正确返回：返回地址正确在高级语言（编译程序）中，是利用“递归工作栈”来实现递归调用的。f(n)f(n-1)f(n-2)f(1)f(0)调用时执行入栈操作保存现场，返回时执行出栈操作恢复现场。…调用返回调用点PnPn-1Pn-2P11层层向下递归，

6、退出时的次序正好相反：递归次序n!(n-1)!(n-2)!1!0!=1返回次序工作记录：返回地址参　数（函数名、引用参数与数组参数等）局部变量函数递归时的活动记录“当前活动工作记录”递归工作栈局部变量返回地址参数……局部变量返回地址参数程序运行期间一个函数调用另一个函数之前需作三件事：（1）将所有的实在参数、返回地址等信息传递给被调用函数保存；（2）为被调用函数的局部变量分配存储区；（3）将控制转以移到被调函数的入口。从被调函数返回调用函数之前需作三件事：（1）保存被调函数的计算结果；（2）释放被调函数的数据区；（3）依照被调函数保存的返回地址将控制转

7、移到调用函数。；注意：（1）有递归函数调用时进栈；（2）递归函数结束时，若栈不空则出栈；（3）递归函数结束时，栈空程序结束。；longFactorial(longn){if(n==0)return1;elsereturnn*Factorial(n-1);//函数调用L1:}voidmain(){intResult;Result=Factorial(4);L0:}函数调用举例计算Factorial时活动记录的内容栈底过程调用举例//中序遍历以t为根的子树,C++实现voidBinTree::InOrder(BinTreeNode*t){if(

8、t!=NULL){InOrder(t→left);//过程调用cout<