数据结构C递归课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,/44,一、递归,递归是程序设计中最有力的方法之一。,优点：,采用,递归,编出的程序简洁、清晰，程序结构符合结构化程序设计，可读性好。,问题：,编译程序是如何处理这类带有递归调用功能的程序的？如果使用了无递归功能的程序设计语言，应该如何设计和实现这类程序呢？,1,一、递归递归是程序设计中最有力的方法之一。1,一、递归,递归,:,在定义自身的同时又出现了对自身的调用。,直接递归函数,:,如果一个函数在其定义体内直接调用自己，则称直接递归函数。,间接递归函数：,如果一个函数经过一系列的中间调用语句，通过其它函数间接调用自己，则称间接递归函数,。,2,一、递归递归:在定义自身的同时又出现了对自身的调用。2,数学中常常利用递归手段来定义一些概念，如求阶乘的运算。,n,的阶乘定义为：,n*(n 1)!,n0,n!=1,n=0,例如,:,显然，该递归的出口是,0!=1,。,3,数学中常常利用递归手段来定义一些概念，如求阶乘的运算。n的阶,求阶乘的算法如下：,long fac(int n),long p;,if (n=0|n=1)p=1;,else p=n*fac(n-1);,return p;,void main(),long x=fac(5);,cout0,的一般情况可采用如下分治策略进行移动,（,1,）将,1,至,n-1,号盘从,a,轴移动至,b,轴，可递归求解,Hanoi(n-1,a,c,b),；,（,2,）将,n,号盘从,a,轴移动至,c,轴；,（,3,）将,1,至,n-1,号盘从,b,轴移动至,c,轴，可递归求解,Hanoi(n-1,b,a,c),。,10,n阶Hanoi塔问题Hanoi(n,a,例：,分析,Hanoi,塔问题移动圆盘的次数,设,T(n),表示,n,个圆盘的,Hanoi,塔问题移动圆盘的次数，显然,T(0)=0,，对于,n0,的一般情况采用如下分治策略：,（,1,）将,1,至,n-1,号盘从,a,轴移动至,b,轴，可递归求解,Hanoi(n-1,a,c,b),；,（,2,）将,n,号盘从,a,轴移动至,c,轴；,（,3,）将,1,至,n-1,号盘从,b,轴移动至,c,轴，可递归求解,Hanoi(n-1,b,a,c),。,在（,1,）与（,3,）中需要移动圆盘次数,T(n-1),，（,2,）需要移动一次圆盘。可得如下的关系：,T(n)=2T(n-1)+1,展开上式可得：,T(n)=2T(n-1)+1,=22T(n-2)+1+1,=2,2,T(n-2)+1+2,=2,n,T(n-n)+1+2+2,n-1,=2,n,-1,11,例：分析Hanoi塔问题移动圆盘的次数 设T(,二、汉诺塔问题的递归算法,void Hanoi(int n,char x,char y,char z),if(n=1),move(x,1,z);,else,Hanoi(n-1,x,z,y);,move(x,n,z);,Hanoi(n-1,y,x,z);,0123456789,void move(char x,int n,char y),cout,移动,n,号盘子,从柱子,x,到柱子,y;,12,二、汉诺塔问题的递归算法void Hanoi(int n,Hanoi(n,x,y,z),可以分成三个子问题：,问题,1.Hanoi(n-1,x,z,y),/,将,X,柱上的,n-1,个圆盘借助,Z,柱移到,Y,柱上，此时,X,柱只剩下第,n,个圆盘；,问题,2.Move(n,x,，,z),/,将,X,柱上的第,n,个移动到,Z,柱,问题,3.Hanoi(n-1,y,x,z),/,将,Y,柱上的,n-1,个圆盘借助,X,柱移到,Z,柱上；,n=1,时可以直接求解,13,Hanoi(n,x,y,z)可以分成三个子问题：13,void Hanoi(int n,char x,char y,char z),if(n=1),move(x,1,z);,else,Hanoi(n-1,x,z,y);,move(x,n,z);,Hanoi(n-1,y,x,z);,0,1,2,3,45,6789,0,3,a,b,c,a,b,c,1,2,4,5,1,递归,层次,运行语句序号,递归工作栈状态,（返址，盘号，,x,y,z,）,塔与圆盘的状态,盘号,123,14,void Hanoi(int n,char x,char,void Hanoi(int n,char x,char y,char z),if(n=1),move(x,1,z);,else,Hanoi(n-1,x,z,y);,move(x,n,z);,Hanoi(n-1,y,x,z);,0,1,2,3,45,6789,0,3,a,b,c,a,b,c,1,2,4,5,2,递归,层次,运行语句序号,递归工作栈状态,（返址，盘号，,x,y,z,）,塔与圆盘的状态,6,2,a,c,b,盘号,123,15,void Hanoi(int n,char x,char,void Hanoi(int n,char x,char y,char z),if(n=1),move(x,1,z);,else,Hanoi(n-1,x,z,y);,move(x,n,z);,Hanoi(n-1,y,x,z);,0,1,23,45678,9,0,3,a,b,c,a,b,c,1,2,3,9,3,递归,层次,运行语句序号,递归工作栈状态,（返址，盘号，,x,y,z,）,塔与圆盘的状态,6,2,a,c,b,6,1,a,b,c,盘号,123,16,void Hanoi(int n,char x,char,void Hanoi(int n,char x,char y,char z),if(n=1),move(x,1,z);,else,Hanoi(n-1,x,z,y);,move(x,n,z);,Hanoi(n-1,y,x,z);,012345,6,7,89,0,3,a,b,c,a,b,c,6,7,2,递归,层次,运行语句序号,递归工作栈状态,（返址，盘号，,x,y,z,）,塔与圆盘的状态,6,2,a,c,b,盘号,123,17,void Hanoi(int n,char x,char,void Hanoi(int n,char x,char y,char z),if(n=1),move(x,1,z);,else,Hanoi(n-1,x,z,y);,move(x,n,z);,Hanoi(n-1,y,x,z);,0,1,23,45678,9,0,3,a,b,c,a,b,c,1,2,3,9,3,递归,层次,运行语句序号,递归工作栈状态,（返址，盘号，,x,y,z,）,塔与圆盘的状态,6,2,a,c,b,8,1,c,a,b,盘号,123,18,void Hanoi(int n,char x,char,void Hanoi(int n,char x,char y,char z),if(n=1),move(x,1,z);,else,Hanoi(n-1,x,z,y);,move(x,n,z);,Hanoi(n-1,y,x,z);,01234567,89,0,3,a,b,c,a,b,c,8,9,2,递归,层次,运行语句序号,递归工作栈状态,（返址，盘号，,x,y,z,）,塔与圆盘的状态,6,2,a,c,b,盘号,123,19,void Hanoi(int n,char x,char,void Hanoi(int n,char x,char y,char z),if(n=1),move(x,1,z);,else,Hanoi(n-1,x,z,y);,move(x,n,z);,Hanoi(n-1,y,x,z);,012345,67,89,0,3,a,b,c,a,b,c,6,7,1,递归,层次,运行语句序号,递归工作栈状态,（返址，盘号，,x,y,z,）,塔与圆盘的状态,盘号,123,20,void Hanoi(int n,char x,char,void Hanoi(int n,char x,char y,char z),if(n=1),move(x,1,z);,else,Hanoi(n-1,x,z,y);,move(x,n,z);,Hanoi(n-1,y,x,z);,0,1,2,3,45,6789,0,3,a,b,c,a,b,c,1,2,4,5,2,递归,层次,运行语句序号,递归工作栈状态,（返址，盘号，,x,y,z,）,塔与圆盘的状态,8,2,b,a,c,盘号,123,21,void Hanoi(int n,char x,char,void Hanoi(int n,char x,char y,char z),if(n=1),move(x,1,z);,else,Hanoi(n-1,x,z,y);,move(x,n,z);,Hanoi(n-1,y,x,z);,0,1,23,456789,0,3,a,b,c,a,b,c,1,2,3,9,3,递归,层次,运行语句序号,递归工作栈状态,（返址，盘号，,x,y,z,）,塔与圆盘的状态,8,2,b,a,c,8,1,b,c,a,盘号,123,22,void Hanoi(int n,char x,char,void Hanoi(int n,char x,char y,char z),if(n=1),move(x,1,z);,else,Hanoi(n-1,x,z,y);,move(x,n,z);,Hanoi(n-1,y,x,z);,012345,67,89,0,3,a,b,c,a,b,c,6,7,2,递归,层次,运行语句序号,递归工作栈状态,（返址，盘号，,x,y,z,）,塔与圆盘的状态,8,2,b,a,c,盘号,123,23,void Hanoi(int n,char x,char,void Hanoi(int n,char x,char y,char z),if(n=1),move(x,1,z);,else,Hanoi(n-1,x,z,y);,move(x,n,z);,Hanoi(n-1,y,x,z);,0,1,23,45678,9,0,3,a,b,c,a,b,c,1,2,3,9,3,递归,层次,运行语句序号,递归工作栈状态,（返址，盘号，,x,y,z,）,塔与圆盘的状态,8,2,b,a,c,8,1,a,b,c,盘号,123,24,void Hanoi(int n,char x,char,void Hanoi(int n,char x,char y,char z),if(n=1),move(x,1,z);,else,Hanoi(n-1,x,z,y);,move(x,n,z);,Hanoi(n-1,y,x,z);,01234567,8,9,0,3,a,b,c,a,b,c,8,9,2,递归,层次,运行语句序号,递归工作栈状态,（返址，盘号，,x,y,z,）,塔与圆盘的状态,8,2,b,a,c,盘号,123,25,void Hanoi(int n,char x,char,void Hanoi(int n,char x,char y,char z),if(n=1),move(x,1,z);,else,Hanoi(n-1,x,z,y);,move(x,n,z);,Hanoi(n-1,y,x,z);,01234567,8,9,0,3,a,b,c,a,b,c,8,9,1,递归,层次,运行语句序号,递归工作栈状态,（返址，盘号，,x,y,z,）,塔与圆盘的状态,盘号,123,26,void Hanoi(int n,char x,char,void Hanoi(int n,char x,char y,char z),if(n=1),move(x,1,z);,else,Hanoi(n-1,x,z,y);,move(x,n,z);,Hanoi(n-1,y,x,z);,0123456789,栈空,a,b,c,0,递归,层次,运行语句序号,递归工作栈状态,（返址，盘号，,