第5章 递归 5.1 什么是递归 5.2 递归算法的设计 本章小结.

Presentation on theme: "第5章 递归 5.1 什么是递归 5.2 递归算法的设计 本章小结."— Presentation transcript:

1 第5章 递归 5.1 什么是递归 5.2 递归算法的设计 本章小结

2 5.1 什么是递归 5.1.1 递归的定义 在定义一个过程或函数时出现调用本过程或本函数的成分，称之为递归。若调用自身,称之为直接递归。若过程或函数p调用过程或函数q，而q又调用p，称之为间接递归。 如果一个递归过程或递归函数中递归调用语句是最后一条执行语句，则称这种递归调用为尾递归。

3 例如，以下是求n!（n为正整数）的递归函数。 int fun(int n)
{ if (n==1) //语句1 return 1; //语句2 else //语句3 return fun(n-1)*n; //语句4 } 在该函数fun(n)求解过程中，直接调用fun(n-1)（语句4）自身，所以它是一个直接递归函数。又由于递归调用是最后一条语句，所以它又属于尾递归。

4 5.1.2 何时使用递归 在以下三种情况下,常常要用到递归的方法。 1. 定义是递归的
有许多数学公式、数列等的定义是递归的。例如,求n!和Fibonacci数列等。这些问题的求解过程可以将其递归定义直接转化为对应的递归算法。 思考题：指出正整数的定义。

5 有些数据结构是递归的。例如,第2章中介绍过的单链表就是一种递归数据结构，其结点类型定义如下：
2. 数据结构是递归的 有些数据结构是递归的。例如,第2章中介绍过的单链表就是一种递归数据结构，其结点类型定义如下： typedef struct LNode { ElemType data; struct LNode *next; } LinkList; 该定义中，结构体LNode的定义中用到了它自身，即指针域next是一种指向自身类型的指针，所以它是一种递归数据结构。 为什么可以这样递归定义类型

6 对于递归数据结构,采用递归的方法编写算法既方便又有效。例如，求一个不带头结点的单链表L的所有data域（假设为int型）之和的递归算法如下：
int Sum(LinkList *L) { if (L==NULL) return 0; else return(L->data+Sum(L->next)); }

7 3. 问题的求解方法是递归的 有些问题的解法是递归的，典型的有Hanoi问题求解，该问题描述是：设有3个分别命名为X,Y和Z的塔座，在塔座X上有n个直径各不相同，从小到大依次编号为1,2,…,n的盘片，现要求将X塔座上的n个盘片移到塔座Z上并仍按同样顺序叠放。 　　盘片移动时必须遵守以下规则：每次只能移动一个盘片；盘片可以插在X、Y和Z中任一塔座；任何时候都不能将一个较大的盘片放在较小的盘片上。设计递归求解算法，并将其转换为非递归算法。 设Hanoi(n,x,y,z)表示将n个盘片从x通过y移动到z上，递归分解的过程是：

8 Hanoi(n-1,x,z,y)； move(n,x,z):将第n个圆盘从x移到z； Hanoi(n-1,y,x,z) Hanoi(n,x,y,z)

9 递归模型是递归算法的抽象，它反映一个递归问题的递归结构。例如前面的递归算法对应的递归模型如下：
5.1.3 递归模型 递归模型是递归算法的抽象，它反映一个递归问题的递归结构。例如前面的递归算法对应的递归模型如下： fun(1)= (1) fun(n)=n*fun(n-1) n>1 (2) 其中，第一个式子给出了递归的终止条件，第二个式子给出了fun(n)的值与fun(n-1)的值之间的关系，我们把第一个式子称为递归出口，把第二个式子称为递归体。

10 一般地，一个递归模型是由递归出口和递归体两部分组成，前者确定递归到何时结束,后者确定递归求解时的递推关系。递归出口的一般格式如下：
f(s1)=m (5.1) 这里的s1与m1均为常量,有些递归问题可能有几个递归出口。递归体的一般格式如下： f(sn+1)=g(f(si),f(si+1),…,f(sn),cj,cj+1,…,cm) (5.2) 其中，n、i、j和m均为正整数。这里的sn+1是一个递归“大问题”，si、si+1、…、sn为递归“小问题”，cj、cj+1、…、cm是若干个可以直接（用非递归方法）解决的问题，g是一个非递归函数，可以直接求值。

11 递归思路是： 　　把一个不能或不好直接求解的“大问题”转化成一个或几个“小问题”来解决； 　　再把这些“小问题”进一步分解成更小的“小问题”来解决； 　　如此分解，直至每个“小问题”都可以直接解决（此时分解到递归出口）。但递归分解不是随意的分解，递归分解要保证“大问题”与“小问题”相似，即求解过程与环境都相似。

12 为了讨论方便，简化上述递归模型为： f(s1)=m1 (5.3) f(sn)=g(f(sn-1),cn-1) (5.4) 求f(sn)的分解过程如下： f(sn) ↓ f(sn-1) … f(s2) f(s1)

13 　一旦遇到递归出口,分解过程结束，开始求值过程，所以分解过程是“量变”过程，即原来的“大问题”在慢慢变小，但尚未解决，遇到递归出口后，便发生了“质变”,即原递归问题便转化成直接问题。上面的求值过程如下：
f(s1)=m1 ↓ f(s2)=g(f(s1),c1) f(s3)=g(f(s2),c2) … f(sn)=g(f(sn-1),cn-1)

14 这样f(sn)便计算出来了，因此递归的执行过程由分解和求值两部分构成。

15 求解fun(5)的过程如下：

16 F(n)=F(n-1)+F(n-2) n>=2
递归树

17 思考题： 　　递归的本质是什么？

18 5.2 递归算法的设计 递归的求解的过程均有这样的特征： 先将整个问题划分为若干个子问题，通过分别求解子问题，最后获得整个问题的解。
　 先将整个问题划分为若干个子问题，通过分别求解子问题，最后获得整个问题的解。 而这些子问题具有与原问题相同的求解方法，于是可以再将它们划分成若干个子问题，分别求解，如此反复进行，直到不能再划分成子问题，或已经可以求解为止。这种自上而下将问题分解、求解,再自上而下引用、合并，求出最后解答的过程称为递归求解过程。这是一种分而治之的算法设计方法。 递归算法设计先要给出递归模型，再转换成对应的C/C++语言函数。

19 　求递归模型的步骤如下： （1）对原问题f(s)进行分析，假设出合理的“较小问题”f(s‘)（与数学归纳法中假设n=k-1时等式成立相似）； （2）假设f(s‘)是可解的,在此基础上确定f(s)的解，即给出f(s)与f(s’)之间的关系（与数学归纳法中求证n=k时等式成立的过程相似）； （3）确定一个特定情况（如f(1)或f(0)）的解,由此作为递归出口（与数学归纳法中求证n=1时等式成立相似）。

20 例如,采用递归算法求实数数组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])，其中MIN()为求两个值较小值函数。因此得到如下递归模型： f(A,i)=A[0] 当i=0时 f(A,i)= MIN(f(A,i-1),A[i]) 其他情况

21 float f(float A[],int 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]; return m; }

22 例如，设计不带头结点的单链表的相关递归算法
f(L)：大问题 L ... a1 a2 an f(L->next)：小问题 为什么在设计单链表的递归算法时不带头节点？

23 f(L)=f(L->next)+1 其他情况
（1）求单链表中数据结点个数 递归模型如下： f(L)=0 当L=NULL f(L)=f(L->next)+1 其他情况 递归算法如下： int count(Node *L) { if (L==NULL) return 0; else return count(L->next)+1; }

24 （2）正向显示以L为首节点指针的单链表的所有节点值
递归模型如下： f(L)不做任何事件 当L=NULL f(L)输出L->data;f(L->next) 其他情况 递归算法如下： void traverse(Node *L) {　if (L==NULL) return; printf("%d ",L->data); traverse(L->next); }

25 （3）反向显示以L为首节点指针的单链表的所有节点值
递归模型如下： f(L)不做任何事件 当L=NULL f(L)f(L->next);输出L->data; 其他情况 递归算法如下： void traverseR(Node *L) {　if (L==NULL) return; traverseR(L->next); printf("%d ",L->data); }

26 （4）删除以L为首节点指针的单链表中值为x的第一个节点
递归模型如下： f(L,x)不做任何事件 当L=NULL f(L,x)  删除L所指结点 当L->data=x f(L,x)f(L->next,x) 其他情况 递归算法如下： void del(Node *&L,ElemType x) { Node *t; if (L==NULL) return; if (L->data==x) { t=L; L=L->next; free(t); return; } else del(L->next,x);

27 （5）删除以L为首节点指针的单链表中值为x的所有节点
递归模型如下： f(L,x)不做任何事件 当L=NULL f(L,x)  删除L所指结点;f(L->next,x) 当L->data=x f(L,x) f(L->next,x) 其他情况 递归算法如下： void delall(Node *&L,ElemType x) { Node *t; if (L==NULL) return; if (L->data==x) { t=L; L=L->next; free(t); delall(L,x); } else delall(L->next,x);

28 （6）输出以L为首节点指针的单链表中最大节点值
递归模型如下： f(L)=L->data 当L中只有一个结点 f(L)=MAX(f(L->next),L->data) 其他情况 递归算法如下： ElemType maxv(Node *L) { ElemType m; if (L->next==NULL) return L->data; m=maxv(L->next); if (m>L->data) return m; else return L->data; }

29 （7）输出以L为首节点指针的单链表中最小节点值。
递归模型如下： f(L)=L->data 当L中只有一个结点 f(L)=MIN(f(L->next),L->data) 其他情况 递归算法如下： ElemType minv(Node *L) { ElemType m; if (L->next==NULL) return L->data; m=minv(L->next); if (m>L->data) return L->data; else return m; }

30 （8）释放L为首节点指针的单链表的所有节点
递归模型如下： f(L)不做任何事件 当L=NULL f(L)f(L->next);释放L所指结点; 其他情况 递归算法如下： void Destroy(Node *L) {　if (L==NULL) return; Destroy(L->next); free(L); }

31 　　 例如，采用递归算法求解皇后问题：在n×n的方格棋盘上，放置n个皇后，要求每个皇后不同行、不同列、不同左右对角线。
6皇后问题的4个解:

32 　　采用整数数组q[N]求解结果，因为每行只能放一个皇后，q[i]（1≤i≤n）的值表示第i个皇后所在的列号，即该皇后放在(i,q[i])的位置上。
　　设queen(k,n)是在1～k-1行上已经放行了k-1个皇后，用于在k～n行放置n-k+1个皇后，则queen(k+1,n)表示在1～k行上已经放好了k个皇后，用于在k+1～n行放置n-k个皇后。显然queen(k+1,n)比queen(k,n)少放置一个皇后。 设queen(k+1,n)是“小问题”，queen(k,n)是“大问题”，则求解皇后问题的递归模型如下： queen(k,n)  n个皇后放置完毕，输出解 　 若k>n queen(k,n)  对于第k行的每个合适的位置i, 　　　　　 在其上放置一个皇后; 其他情况 queen(k+1,n);

33 得到递归过程如下： void queen(int k,int n) { if (k>n) 输出一个解; else
for (j=1;j<=n;j++) //在第k行找所有的列位置 if (第k行的第j列合适) { 在(k,j)位置处放一个皇后即q[k]=j queen(k+1,n); }

34 int q[N]; //存放各皇后所在的列号
对于(k,j)位置上的皇后，是否与已放好的皇后(i,q[i])（1≤i≤k-1）有冲突呢？ 只要满足以下条件，则存在冲突，否则不冲突： (q[i]==j) || (abs(q[i]-j)==abs(k-i))

35 int place(int k,int j) //测试(k,j)位置能否摆放皇后
{ int i=1; while (i<k) //i=1～k-1是已放置了皇后的行 { if ((q[i]==j) || (abs(q[i]-j)==abs(k-i))) return 0; i++; } return 1;

36 void queen(int k,int n) //放置1～k的皇后
{ int j; if (k>n) print(n); //所有皇后放置结束 else for (j=1;j<=n;j++) //在第k行上穷举每一个位置 if (place(k,j)) //在第k行上找到一个合适位置(k,j) { q[k]=j; queen(k+1,n); }

37 用栈求解皇后问题: void queen(int n) //求解n皇后问题 { int i,j,k; bool find;
StType st; //定义栈st st.top=0; //初始化栈顶指针 st.top++; //将(1,1)进栈 st.col[st.top]=1; while (st.top>0) //栈不空时循环 { i=st.top; //当前皇后为第i个皇后 if (st.top==n) //所有皇后均放好,输出一个解 { printf(" 第%d个解：",++count); for (k=1;k<=st.top;k++) printf("(%d,%d) ",k,st.col[k]); printf("\n"); }

38 find=false; for (j=1;j<=n;j++) if (place(st,i+1,j)) //在i+1行找到一个放皇后的位置(i+1,j) { st.top++; st.col[st.top]=j; find=true; break; }

39 if (find==false) //在i+1行找不到放皇后的位置,回溯
{ while (st.top>0) { if (st.col[st.top]==n) //本行没有可放位置,退栈 st.top--; for (j=st.col[st.top]+1;j<=n;j++) //在本行找下一个位置 if (place(st,st.top,j)) { st.col[st.top]=j; break; } if (j>n) //当前皇后在本行没有可放的位置 st.top--; //退栈 else //本行找到一个位置后退出回溯

40 本章小结 本章基本学习要点如下： （1）理解递归的定义和递归模型。 （2）重点掌握递归的执行过程。 （3）掌握递归设计的一般方法。
（4）灵活运用递归算法解决一些较复杂应用问题。

41 练习题5 　　　5.1和5.2题。