第5章递归讲述.ppt

Hanoi问题 n阶Hanoi塔问题：假设有三个分别命名为X、Y、Z的塔座，在X塔座上插有n个直径大小各不相同，依小到大编号为1，2，…，n的圆盘，要求：把X上的n个圆盘移到Z上，排列顺序相同，移动规则为： 每次只能移动一个圆盘； 圆盘可以在任一塔上做多次移动； 在任何时刻，大盘不能压小盘； Hanoi问题 void Hanoi( int n, char x, char y, char z ) { if( n == 1 ) Move( 1, x, z ); // 把1号盘，从x移到z else { Hanoi( n – 1, x, z, y );// 把n-1个盘，从x移到y，z为辅助塔 Move( n, x, z ); // 把n号盘，从x移到z Hanoi( n – 1, y, x, z );//把n-1个盘，从y移到z，x为辅助塔 } } 递归求n！ 递归调用的实现原理 返回时，执行出栈操作，把当前栈顶保留的值送回相应的参数中进行恢复，并按栈顶中的返回地址，从断点处继续执行。 例5.2 利用串的基本运算写出对串求逆的递归算法。 递归模型： s s为空串 f(s)= Concat(f(SubStr(s,2,StrLength(s)-1)),SubStr(s,1,1)) 其他 SqString invert(SqString s) { SqString s1,s2; if(StrLength(s)0) { s1=invert(SubStr(s,2,StrLength(s)-1)); s2=Concat(s1,SubStr(s,1,1)); } else StrCopy(s2,s); return s2; } 例5.3 求顺序表{a1,a2,…,an}中的最大元素。 解：将线性表分解成{a1,a2,…,am}和{am+1,…,an}两个子表，分别求得子表中的最大元素ai和aj，比较ai和aj中的大者，就可以求得整个线性表的最大元素。 而求解子表中的最大元素方法与总表相同，即再分别将它们分成两个更小的子表，如此不断分解，直到表中只有一个元素为止。 ElemType Max(SqList L,int i,int j) { int mid; ElemType max,max1,max2; if(i==j) max=L.data[i]; else { mid=(i+j)/2; max1=Max(L,i,mid); max2=Max(L,mid+1,j); max=(max1max2)?max1:max2; } return(max); } * * 第5章 递归 5.3 递归算法的设计 5.1 什么是递归 5.2 递归调用的实现原理 5.1.1 递归的定义 递归：在定义一个过程或函数时出现调用本过程或本函数的成分。 直接递归：调用自身。 间接递归：若函数p调用函数q，而q又调用p。 尾递归：一个递归函数中递归调用语句是最后一条执行语句。 5.1 什么是递归 例5.1 以下是求n!(n为正整数)的递归函数。 int fun(int n) { if (n==1) /*语句1*/ return 1; /*语句2*/ else /*语句3*/ return fun(n-1)*n; /*语句4*/ } 递归可以把一个大型复杂的问题转化为一个或多个与原问题相似的规模较小的问题来求解，通过少量的语句，实现重复计算。 体现了分而治之的算法思想 在以下3种情况下，常常要用到递归的方法。 1. 定义是递归的 2. 数据结构是递归的 例如，单链表就是一种递归的数据结构，其结点类型定义如下： typedef struct LNode { ElemType data; struct LNode *next; } LinkList; 该定义中，结构体LNode的定义中用到了它自身，即指针域next是一种指向自身类型的指针。 5.1.2 何时使用递归 求n!和Fibonacci数列 【举例】求一个不带头结点的单链表L的所有data域(假设为int型)之和。 int Sum(LinkList *L) { if (L==NULL) return 0; else return(L-