第6周递归第2讲-递归算法的设计.pdf
设计求解问题的递归模型。设计求解问题的递归模型。 转换转换成成对应对应的递归算法。的递归算法。 5.2.1 递归递归算法设计的步骤算法设计的步骤 递归算法递归算法 （1）对原问题对原问题f(s)进行分析进行分析，称为称为“大问题大问题”， 假设出合理的假设出合理的“小问题小问题”f(s) ； 求递归模型求递归模型的的步骤步骤 （3）确定一个特定情况（如）确定一个特定情况（如f(1)或或f(0)）的的解解 递归出口递归出口。 （2）假设假设f(s)是可是可解解的的，在此在此基础上确定基础上确定f(s) 的解的解，即给出即给出f(s)与与f(s)之间之间的的关系关系 递归体递归体。 数学归纳法数学归纳法 假设假设n=k- -1时等式时等式 成立，求证成立，求证n=k时时 等式成立等式成立 求证求证n=1时等式时等式 成立成立 例如例如，采用递归算法求实数数组采用递归算法求实数数组A0.n- -1中的最小值中的最小值。 假设假设f(A,i)求求数组元素数组元素A0Ai（i+1个元素个元素）中中的最小值的最小值。 f(A,i)=A0当当i=0时时 f(A,i)= MIN(f(A,i- -1)，Ai) 其他情况其他情况 因此得到如下递归模型：因此得到如下递归模型： 假设假设f(A,i- -1)已求出已求出，则则f(A,i)=MIN(f(A,i- -1)，Ai)，其中其中MIN() 为求两个值较小值函数为求两个值较小值函数。 A0 A1 Ai- -1 Ai An- -1 f(A,i)：大问题，处理大问题，处理i+1个元素个元素 f(A,i- -1)：小问题，处理小问题，处理i个元素个元素 当当i=0时，只有一个元素，有时，只有一个元素，有f(A,i)=A0。 float f(floatA,int i) float m; if (i=0) returnA0; else m=f(A,i-1); if (mAi) returnAi; else return m; 由此得到如下递归求解算法：由此得到如下递归求解算法： 递归出口递归出口 递归体递归体 递归数据结构的数据特别适合递归处理递归数据结构的数据特别适合递归处理 递归递归算法算法 种瓜得瓜种瓜得瓜：递归性：递归性 5.2.2 基于递归基于递归数据结构的递归算法设计数据结构的递归算法设计 数据：数据：D=瓜的集合瓜的集合 运算：运算：Op=种瓜种瓜 递归性：递归性： Op(x D) D 【例例5- -1】设计设计不不带头节点的带头节点的单链表的相关递归单链表的相关递归算法。算法。 a1a2an . L f(L)：大问题：大问题 f(L- -next)：小问题：小问题 把“大问题”转化为若干个把“大问题”转化为若干个相似相似的“小问题”来求解。的“小问题”来求解。 为什么在这里设计为什么在这里设计单链表的递归算法时不单链表的递归算法时不带头节点？带头节点？ L- -next) 求求单链表中单链表中数据节点个数数据节点个数。 f(L)f(L- -next) a1a2 .Lan 设设f(L)为单链表中数据节点个数。为单链表中数据节点个数。 空单链表的数据节点个数为空单链表的数据节点个数为0f(L)=0当当L=NULL 对于非空单链表：对于非空单链表： =+ 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; 不带头节点单链表不带头节点单链表L 正向正向显示显示所有节点值所有节点值。 反向反向显示显示所有节点值所有节点值。 a1a2an.L f(L)：大大问题，输出问题，输出a1,a2,an f(L- -next)：小小问题，输出问题，输出a2,an 假设假设f(L- -next)已求解已求解 f(L) 输出输出L- -data； f(L- -next); 假设假设f(L- -next)已求解已求解 f(L) f(L- -next);输出输出L- -data； f(L)：大大问题，输出问题，输出an,a2a1 f(L- -next)：小小问题，输出问题，输出an,a2 递归模型如下：递归模型如下： f(L) 不不做任何做任何事件事件 当当L=NULL f(L) 输出输出L-data;f(L-next) 其他其他情况情况 递归模型如下：递归模型如下： f(L) 不不做任何做任何事件事件 当当L=NULL f(L) f(L-next);输出输出L-data 其他其他情况情况 不带头节点单链表不带头节点单链表L 正向正向显示显示所有节点值所有节点值。反向反向显示显示所有节点值所有节点值。 void traverse(Node *L) if (L=NULL) return; printf(%d ,L-data); traverse(L-next); void traverseR(Node *L) if (L=NULL) return; traverseR(L-next); printf(%d ,L-data); 5.3.3 基于递归基于递归求解方法的递归算法设计求解方法的递归算法设计 有些问题可以采用递归方法求解（求解方法之一）。有些问题可以采用递归方法求解（求解方法之一）。 采用采用递归递归方法方法求解问题时，求解问题时，需要对问题本身进行分析，确定需要对问题本身进行分析，确定 大、小问题解之间的关系，构造合理的递归体。大、小问题解之间的关系，构造合理的递归体。 大问题大问题 小问题小问题1小问题小问题2 关系关系？ 【例例5- -2】采用递归算法求解迷宫问题，并输出从入口到采用递归算法求解迷宫问题，并输出从入口到 出口的所有迷宫路径。出口的所有迷宫路径。 求解问题描述：求解问题描述： (xi，yi)(xe，ye) mgpath(xi,yi,xe,ye,path) 出口出口 mgpath(int xi,int yi,int xe,int ye,PathType path)： 求从求从(xi,yi)到到(xe,ye)的迷宫路径，用的迷宫路径，用path变量保存迷宫路径。变量保存迷宫路径。 入入口口 (xi，yi)(xe，ye) mgpath(xi,yi,xe,ye,path) 出口出口 大问题大问题 入入口口 (i，j)(xi，yi) 走一步走一步 (xe，ye) mgpath(i,j,xe,ye,path) 出口出口 小问题小问题 大问题大问题 走一步走一步 + + 小问题小问题 入入口口 mgpath(xi,yi,xe,ye,path) 将将(xi,yi)添加到添加到path中中;输出输出path中的迷宫路径中的迷宫路径; 若若(xi,yi)=(xe,ye) mgpath(xi,yi,xe,ye,path) 对于对于(xi,yi)四周的每一个相邻方块四周的每一个相邻方块(i,j)： 将将(xi,yi)添加到添加到path中中; 置置mgxiyi=- -1; mgpath(i,j,xe,ye,path); path回退一步并置回退一步并置mgxiyi=0; 若若(xi,yi)不为出口且可走不为出口且可走 求解迷宫问题的递归模型如下：求解迷宫问题的递归模型如下： 在一个“小问题”在一个“小问题”执执 行完后回退找行完后回退找所有解所有解 迷宫迷宫路径用顺序表存储，它的元素由方块构成的。路径用顺序表存储，它的元素由方块构成的。 其其PathType类型定义如下：类型定义如下： typedef struct int i;/当前方块的行号当前方块的行号 int j;/当前方块的列号当前方块的列号 Box; typedef struct Box dataMaxSize; int length;/路径长度路径长度 PathType;/定义路径类型定义路径类型 void mgpath(int xi,int yi,int xe,int ye,PathType path) /求解路径为求解路径为:(xi,yi) (xe,ye) int di,k,i,j; if (xi=xe path.datapath.length.j = yi; path.length+; printf(迷宫路径迷宫路径%d如下如下:n,+count); for (k=0;k<path.length;k+) printf(t(%d,%d),path.datak.i, path.datak.j); if (k+1)%5=0)/每输出每每输出每5个方块后换一行个方块后换一行 printf(n); printf(n); 找到了出口，输出一条路径（递归出口） else/(xi,yi)不是出口不是出口 if (mgxiyi=0)/(xi,yi)是一个可走方块是一个可走方块 di=0; while (di<4) /对于对于(xi,yi)四周的每一个相邻方位四周的每一个相邻方位di switch(di) /找方位找方位di对应的方块对应的方块(i,j) case 0:i=xi-1; j=yi; break; case 1:i=xi; j=yi+1; break; case 2:i=xi+1; j=yi; break; case 3:i=xi; j=yi-1; break; path.datapath.length.i = xi; path.datapath.length.j = yi; path.length+; /路径长度增路径长度增1 mgxiyi=-1; /避免来回重复找路径避免来回重复找路径 mgpath(i,j,xe,ye,path); path.length-;/回退一个方块回退一个方块 mgxiyi=0;/恢复恢复(xi,yi)为可走为可走 di+; /-while /- if (mgxiyi=0) /-递归体递归体 本本算法输出算法输出所有的迷宫所有的迷宫路径路径，可以通过进一步比较，可以通过进一步比较找出最短找出最短 路径（可能存在多条最短路径）。路径（可能存在多条最短路径）。 012345 0 1 2 3 4 5 int mgM+2N+2= /M=4，N=4 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1 ,1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1 ; void main() PathType path; path.length=0; mgpath(1,1,4,4,path); 应用应用 得到如下得到如下4条条迷宫路径：迷宫路径： 迷 宫 路 径 迷 宫 路 径 1 迷 宫 路 径 迷 宫 路 径 2 迷 宫 路 径 迷 宫 路 径 3 迷 宫 路 径 迷 宫 路 径 4 本章完本章完
