栈与递归的实现

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,栈与递归的实现,3月29,1,递归函数的定义,递归函数：是直接调用自己或间接调用自己的函数。,求n！，具体实现如下：,long fact(int n),if(n=0) return 1;,else return n*fact(n-1);,2,递归函数适用的场合,在解决现实问题中，对于求解一个复杂的或者问题规模较大的问题，如果可以将其划分为一些简单的或者规模较小的问题进行解决，如果这种划分满足：,所划分成的子问题性质与原来的大问题相同。,当问题规模小到一定程度的时候直接有解。,对于满足以上条件的问题我们就可以考虑使用递归的方法求解。,3,例子,用辗转相除法求m、n最大公约数,原理：假定m=n,m=p1*n+q1,如果q1=0,则最大公约数为p1。,若q1！=0，则m、n的公约数也应该是q1的公约数，那么问题就转化为求n、q1的最大公约数。,4,G(m,n)=n 若m%n=0,G(m,n)=G(n,m%n) 若m%n!=0,5,具体实现如下,int g(int m,int n),if(m%n=0)return n;,return g(n,m%n);,6,非直观的递归问题,某些问题本身没有明显的递归结构，但可以转化成递归结构。,hanoi塔问题-汉诺塔P55,如果有一个盘子，直接从X移到Z即可。,如果有n个盘子要从X移到Z，Y作为辅助。问题可以转化为，先将上面n-1个从X移动到Y，Z作为辅助，然后将第n个从X移动到Z，最后将剩余的n-1个从Y移动到Z，X作为辅助。,7,例子,void move(char a,char b),/从a移动到b,coutbendl;,void hanoi(int n,char X,char Y,char Z),/把n个盘子从X移动到Z，Y作为辅助,if(n=1) move(X,Z);,else,hanoi(n-1,X,Z,Y);,move(X,Z);,hanoi(n-1,Y,X,Z);,8,递归函数是如何执行的？,环境：高级语言环境,方式：调用函数和被调用函数之间的链接及信息交换通过,栈,进行,9,函数调用期间系统的工作,当一个函数调用另外一个函数时，在运行被调用函数之前，系统需要做三件事：,一：将所有的实在参数，返回地址等信息传递给被调用函数保存,二：释放被调用函数的数据区,三依照被调用函数保存的返回地址，将控制转移到调用函数,10,调用原则,多个函数构 成调用嵌套：按照后调用先返回原则，这样函数之间的信息传递和控制转移必须通过栈实现,解释：系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就为它子栈顶分配一个存储区，每当一个函数退出时，就释放一个存储区，从而当前运行的函数的数据区必须在栈顶,11,n阶Hanoi塔的问题,#include,void hanoi(int n,char x, char y, char z), /将塔座x上按直径有小到大且自上而下编号为1至n的n个圆盘按规则搬动到,/塔座z上,y塔座可以用做辅助move()/搬动函数,if(n=1),move(x,1,z);/当n=1时,则搬动x上的圆盘放到z上,12,else,hanoi(n-1,x,z,y);/将x上编号为1至n-1的圆盘移动到y,z做辅助塔,move(x,n,z);/执行搬动操作,hanoi(n-1,y,x,z);/将y塔座上的编号为1至n-1的圆盘移动到z上,x做辅助塔,13,main(),int n, a, b, c;,.,.,hanoi(n,a,b,c);,14,