PPT《第6章 递归》

上述信息组成一个递归工作记录保存在递归工作栈中,按后进先出的原则组织. 局部变量返回地址参 数 递归工作记录 活动记录框架 返回时,执行出栈操作,把当前栈顶保留的值送回相应的参数中进行恢复,并按栈顶中的返回地址,从断点处继续执行. 局部变量返回地址参 数 递归工作记录 活动记录框架 递归算法设计先要给出递归模型,再转换成对应的C/C++语言函数. 6.3 递归算法的设计 例1:采用递归算法求实数数组A[0..n-1]中的最小值.用函数f(A,i)求数组元素A[0]~A[i]中的最小值.当i=0时,有f(A,i)=A[0];

假设f(A,i-1)已求出,则f(A,i)=MIN(f(A,i-1),A[i])得到如下递归模型:A[0]当i=0时f(A,i)MIN(f(A,i-1),A[i]) 其他情况 由此得到如下递归求解算法: float f(float A[],int i)float m;

if (i==0)return A[0]else { m=f(A,i-1);

if (m>A[i]return A[i];

else return m;

} } 例6.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;

} 例6.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=(max1>max2)?max1:max2;

}return(max);

} (1)理解递归的定义和递归模型. (2)重点掌握递归的执行过程. (3)掌握递归设计的一般方法. 本章小结 10月30日上机:上机实验题4 P111 4.1上机实验题5 P133 5.2