数据结构(C++)递归.ppt

一、递归一、递归 二、汉诺塔问题二、汉诺塔问题 三、递归与非递归的转化三、递归与非递归的转化难点难点 优点：优点：采用采用编出的程序简洁、清晰，程序结编出的程序简洁、清晰，程序结构符合结构化程序设计，可读性好。构符合结构化程序设计，可读性好。编译程序是如何处理这类带有递归调用功编译程序是如何处理这类带有递归调用功能的程序的？如果使用了无递归功能的程序设计能的程序的？如果使用了无递归功能的程序设计语言，应该如何设计和实现这类程序呢？语言，应该如何设计和实现这类程序呢？ 在定义自身的同时又出现了对自身的调用。在定义自身的同时又出现了对自身的调用。如果一个函数在其定义体内直接调如果一个函数在其定义体内直接调用自己，则称直接递归函数。用自己，则称直接递归函数。如果一个函数经过一系列的中间如果一个函数经过一系列的中间调用语句，通过其它函数间接调用自己，则称间调用语句，通过其它函数间接调用自己，则称间接递归函数接递归函数。 数学中常常利用递归手段来定义一些概念，数学中常常利用递归手段来定义一些概念，如求阶乘的运算。如求阶乘的运算。n的阶乘定义为：的阶乘定义为： n * ( n 1 ) ! n0 n! = 1 n=0例如例如: : 显然，该递归的出口是显然，该递归的出口是 0! =1。 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); coutx; long fac (int n) long p; if (n=0 | n=1) p=1; else p=n*fac(n-1) ; return p; 递归函数包含：递归函数包含：1、递归调用语句递归调用语句，如，如 fac (n-1)；2、基值判断基值判断，如，如n=0 | n=1即为基值，保证了递归可以即为基值，保证了递归可以终止，满足基值条件后的计算终止，满足基值条件后的计算 p=1, 一般称为最终计算；一般称为最终计算；3、调用之后的返回处理调用之后的返回处理。如。如 p= n * fac (n-1) ，是返回之，是返回之后要进行的操作。后要进行的操作。fac(5)main()n=5p=5*fac(4)第一层第一层facn=4p=4*fac(3)第二层第二层facn=3p=3*fac(2)第三层第三层facn=2p=2*fac(1)第四层第四层facn=1p=1第五层第五层facfac(2)=2fac(1)=1fac(3)=6fac(4)=24fac(5)=120输出输出假设调用该递归函数的假设调用该递归函数的主函数为主函数为第第0层层，则从主函数调，则从主函数调用递归函数为进入用递归函数为进入第第1层层；从第；从第 i层递归调用本身为进入层递归调用本身为进入“下一层下一层”，即，即第第 i+1 层层。反之，退出第。反之，退出第 i 层递归应返层递归应返回至回至“上一层上一层”，即第，即第 i-1 层。层。递归层次递归层次: : 为了保证递归函数正确执行，系统需设立一个为了保证递归函数正确执行，系统需设立一个“递归递归工作栈工作栈”作为整个递归函数运行期间使用的数据存储区。作为整个递归函数运行期间使用的数据存储区。每一层递归所需信息构成一个每一层递归所需信息构成一个“工作记录工作记录”，其中包括，其中包括所有的实参、所有的局部变量以及上一层的返回地址。所有的实参、所有的局部变量以及上一层的返回地址。 每进入一层递归，就产生一个新的工作记录每进入一层递归，就产生一个新的工作记录压入压入栈顶。栈顶。每退出一层递归就从栈顶每退出一层递归就从栈顶弹出弹出一个工作记录，则当前执一个工作记录，则当前执行层的工作记录必须是递归工作栈栈顶的工作记录，称行层的工作记录必须是递归工作栈栈顶的工作记录，称这个记录为这个记录为“活动记录活动记录”，并称指示活动记录的栈顶指，并称指示活动记录的栈顶指针为针为“当前环境指针当前环境指针”。abc1号盘2号盘3号盘abc1号盘2号盘3号盘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); 0123456789void move (char x, int n, char y) cout移动移动n号盘子号盘子从柱子从柱子x到柱子到柱子y;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时可以直接求解时可以直接求解void Hanoi(intvoid Hanoi(int n, char x, char y, char z) n, char x, char y, char z) if(n = = 1) if(n = = 1) move(x, 1, z); move(x, 1, z); elseelse Hanoi(n-1, x, z, y); Hanoi(n-1, x, z, y);move(x, n, z);move(x, n, z); Hanoi(n-1, y, x, z);Hanoi(n-1, y, x, z); 0123456789 0,3,a,b,cabc1,2,4,51递归递归层次层次运行语运行语句序号句序号递归工作栈状态递归工作栈状态（返址，盘号，（返址，盘号，x,y,z）塔与圆盘的状态塔与圆盘的状态盘号盘号123void Hanoi(intvoid Hanoi(int n, char x, char y, char z) n, char x, char y, char z) if(n = = 1) if(n = = 1) move(x, 1, z); move(x, 1, z); elseelse Hanoi(n-1, x, z, y); Hanoi(n-1, x, z, y);move(x, n, z);move(x, n, z); Hanoi(n-1, y, x, z);Hanoi(n-1, y, x, z); 0123456789 0,3,a,b,cabc1,2,4,52递归递归层次层次运行语运行语句序号句序号递归工作栈状态递归工作栈状态（返址，盘号，（返址，盘号，x,y,z）塔与圆盘的状态塔与圆盘的状态6,2,a,c,b盘号盘号123void Hanoi(intvoid Hanoi(int n, char x, char y, char z) n, char x, char y, char z) if(n = = 1) if(n = = 1) move(x, 1, z); move(x, 1, z); else else Hanoi(n-1, x, z, y); Hanoi(n-1, x, z, y);move(x, n, z);move(x, n, z); Hanoi(n-1, y, x, z);Hanoi(n-1, y, x, z); 0123456789 0,3,a,b,cabc1,2,3,93递归递归层次层次运行语运行语句序号句序号递归工作栈状态递归工作栈状态（返址，盘号，（返址，盘号，x,y,z）塔与圆盘的状态塔与圆盘的状态6,2,a,c,b6,1,a,b,c盘号盘号123void Hanoi(intvoid Hanoi(int n, char x, char y, char z) n, char x, char y, char z) if(n = = 1) if(n = = 1) move(x, 1, z); move(x, 1, z); else else Hanoi(n-1, x, z, y); Hanoi(n-1, x, z, y);move(x, n, z);move(x, n, z); Hanoi(n-1, y, x, z);Hanoi(n-1, y, x, z); 0123456789 0,3,a,b,cabc6,72递归递归层次层次运行语运行语句序号句序号递归工作栈状态递归工作栈状态（返址，盘号，（返址，盘号，x,y,z）塔与圆盘的状态塔与圆盘的状态6,2,a,c,b盘号盘号123void Hanoi(intvoid Hanoi(int n, char x, char y, char z) n, char x, char y, char z) if(n = = 1)if(n = = 1) move(x, 1, z); move(x, 1, z); else else Hanoi(n-1, x, z, y); Hanoi(n-1, x, z, y);move(x, n, z);move(x, n, z); Hanoi(n-1, y, x, z);Hanoi(n-1, y, x, z); 0123456789 0,3,a,b,cabc1,2,3,93递归递归层次层次运行语运行语句序号句序号递归工作栈状态递归工作栈状态（返址，盘号，（返址，盘号，x,y,z）塔与圆盘的状态塔与圆盘的状态6,2,a,c,b8,1,c,a,b盘号盘号123void Hanoi(intvoid Hanoi(int n, char x, char y, char z) n, char x, char y, char z) if(n = = 1) if(n = = 1) move(x, 1, z); move(x, 1, z); else else Hanoi(n-1, x, z, y); Hanoi(n-1, x, z, y);move(x, n, z);move(x, n, z); Hanoi(n-1, y, x, z);Hanoi(n-1, y, x, z); 0123456789 0,3,a,b,cabc8,92递归递归层次层次运行语运行语句序号句序号递归工作栈状态递归工作栈状态（返址，盘号，（返址，盘号，x,y,z）塔与圆盘的状态塔与圆盘的状态6,2,a,c,b盘号盘号123void Hanoi(intvoid Hanoi(int n, char x, char y, char z) n, char x, char y, char z) if(n = = 1) if(n = = 1) move(x, 1, z); move(x, 1, z); else else Hanoi(n-1, x, z, y); Hanoi(n-1, x, z, y);move(x, n, z);move(x, n, z); Hanoi(n-1, y, x, z);Hanoi(n-1, y, x, z); 0123456789 0,3,a,b,cabc6,71递归递归层次层次运行语运行语句序号句序号递归工作栈状态递归工作栈状态（返址，盘号，（返址，盘号，x,y,z）塔与圆盘的状态塔与圆盘的状态盘号盘号123void Hanoi(intvoid Hanoi(int n, char x, char y, char z) n, char x, char y, char z) if(n = = 1) if(n = = 1) move(x, 1, z); move(x, 1, z); elseelse Hanoi(n-1, x, z, y); Hanoi(n-1, x, z, y);move(x, n, z);move(x, n, z); Hanoi(n-1, y, x, z);Hanoi(n-1,