搜索
C语言程序设计尹宝林第四讲：递归2005-1-2C语言程序设计进阶2递归的概念和作用概念或函数直接或间接引用自身在可计算性理论中有重要的地位递归可枚举常用的重要机制概念的表达数据结构和算法的描述重要的思维方式现代程序设计语言中都提供支持2005-1-2C语言程序设计进阶3递归概念的例树树的非递归定义连通且无圈的无向图树的递归定义1.一个节点是一棵树2.一棵树的每个节点可以有m个分支，其中每一个分支都是一棵树3.一棵树中的任意两个节点间只有一条通路2005-1-2C语言程序设计进阶4递归算法的例排序归并排序(mergesort)最典型常用的实现方法是通过递归的定义快速排序算法(quicksort)直接通过递归定义2005-1-2C语言程序设计进阶5递归函数的例直接引用的递归函数：对树的中序遍历typedefstructt_node{intvalue;structt_node*l_tree,*r_tree;}t_node;voidtreat_tree(t_node*treep,void(*op_func)(int)){if(treep==NULL)return;treat_tree(treep-l_tree,op_func);op_func(treep-value);treat_tree(treep-r_tree,op_func);}2005-1-2C语言程序设计进阶6递归函数的例(续)间接引用的递归函数voida(inti){……b(i–1);}voidb(inti){……a(i);}2005-1-2C语言程序设计进阶7递归函数的例(续)递归曲线Hilbert曲线Sierpinski曲线分形（fractal）2005-1-2C语言程序设计进阶8递归在程序设计中的例程序设计语言的语法描述Backus-NaurForm(巴克斯范式）Algol、C、……数据结构控件复杂的嵌套结构……2005-1-2C语言程序设计进阶9递归的优点概念清晰，易于理解描述简单，易于实现例：GUI中的嵌套的选单(Menu)代码紧凑，易于维护2005-1-2C语言程序设计进阶10递归函数的缺点在某些情况下计算复杂度较高不适当的定义引起的重复计算在某些情况下占用存储空间较多深度递归调用引起的资源消耗函数调用的开销计算过程简单时函数调用开销的比例增加2005-1-2C语言程序设计进阶11理解和使用递归的难点递归的基本思维方法递归概念的表示使用递归方法求解问题递归过程的描述方法递归的执行过程递归的使用条件和环境在什么情况下应该使用递归2005-1-2C语言程序设计进阶12递归概念的表示自引用结构例1：二叉树的表示typedefstructtree_node{intvalue;structtree_node*l_tree;structtree_node*r_tree;}tree_node;例2：单向链表的表示typedefstructlist{intvalue;structlist*next;}list;2005-1-2C语言程序设计进阶13递归过程描述的基本思想把问题化为形式相同但规模较小的问题在问题规模缩小到一定的程度时加以解决递归的描述定义对问题可以直接求解的情况和方法用自引用的方式描述问题的一般求解过程在对自身的引用过程中降低问题的复杂度在复杂度降低到一定程度时直接求解2005-1-2C语言程序设计进阶14递归过程描述的基本思想(续)与数学归纳法类似数学归纳法在证明一个关于整数的公式时1.证明该公式对一个整数k成立2.假设该公式对某一整数n成立3.证明该公式对整数n+1成立2005-1-2C语言程序设计进阶15递归过程的描述步骤1.确定递归参数2.定义递归的终止条件和基础计算当递归参数为一个确定的值时应当如何直接进行计算3.定义递归调用当递归参数不满足终止条件时，将计算表示为包含对自身调用的计算对自身调用时递归参数应更接近终止条件2005-1-2C语言程序设计进阶16递归过程描述的例阶乘0!=1n!=n*(n–1)!组合公式Cm1=mCmm=1Cmn=Cnm-1+Cn-1m-12005-1-2C语言程序设计进阶17递归过程描述的例(续)梵塔初始状态：N个(N0)大小不同的圆盘插在柱A上，大盘在下，小盘在上。柱B和柱C上为空任务：将所有的圆盘移到柱B上，仍保持大盘在下，小盘在上的状态限制条件：每次只能移动一个盘可以把圆盘临时放在任一柱上，但大盘不能压住小盘2005-1-2C语言程序设计进阶18递归过程描述的例(续)梵塔问题递归求解的思路当n等于1时直接将盘由柱A移至柱B当n大于1时1.将顶部的n–1个盘由柱A移至柱C2.将底部的大盘由柱A移至柱B3.将柱C上的n–1个盘移至柱B2005-1-2C语言程序设计进阶19递归函数的基本结构基础计算递归的基础条件(终止条件)递归的基础计算递归调用直接或间接的对自身的引用对递归控制参数的修改向着递归终止条件方向变化递归调用时的其它计算计算n的阶乘intfactorial(intn){if(n==0)return1;returnn*factorial(n–1);}计算组合公式intcomb_num(intm,intn){if(mn||m1||n1)//参数错误处理return0;if(n==1)returnm;if(m==n)return1;returncomb_num(m-1,n)+comb_num(m-1,n-1);}使用putchar()打印整数整数向字符串的转换数字的内部和外部表示方式数字表示方式转换时的顺序字符的输出voidprintd(intn){if(n0){putchar('-');n=-n;}if(n/10)printd(n/10);putchar(n%10+'0');}2005-1-2C语言程序设计进阶22递归函数的执行过程初学者的困惑在函数未定义完时对自身调用的执行过程函数的参数和局部变量的值的变化递归函数的执行过程与普通的函数调用相同实际调用发生在执行阶段每一次递归调用产生一个独立的函数运行实例每一个函数运行实例具有独立的变量和参数可看作调用与自身同名且代码相同的另一个函数2005-1-2C语言程序设计进阶23递归函数执行的例：梵塔梵塔函数voidhanoi(intn,intfrom,intto,intvia);辅助函数voidmove(intn,intfrom,intto)；梵塔函数的调用hanoi(3,'A','B','C')；梵塔函数的执行过程voidmove(intn,intfrom,intto){printf(Move(%d,'%c','%c')\n,n,from,to);}voidhanoi(intn,intfrom,intto,intvia){if(n==1){move(n,from,to);//M1return;}hanoi(n–1,from,via,to);//H1move(n,from,to);//M2hanoi(n–1,via,to,from);//H2}......hanoi(3,'A','B','C')；hanoi(3,'A','B','C')hanoi(2,'A','C','B')//H1hanoi(1,'A','B','C')//H1move(1,'A','B')//M1move(2,'A','C')//M2hanoi(1,'B','C','A')//H2move(1,'B','C')//M1move(3,'A','B')//M2hanoi(2,'C','B','A')//H2hanoi(1,'C','A','B')//H1move(1,'C','A')//M1move(2,'C','B')//M2hanoi(1,'A','B','C')//H2move(1,'A','B')//M1执行结果：Move(1,'A','B'),Move(2,'A','C'),Move(1,'B','C')Move(3,'A','B')Move(1,'C','A'),Move(2,'C','B'),Move(1,'A','B')2005-1-2C语言程序设计进阶26递归函数的设计问题分析确定问题中的递归参数确定参数变化范围的下限及其计算方式确定一般情况的处理与简单情况的关系程序设计细化对问题的递归描述确定算法实现时需要考虑的因素选定适当的数据结构2005-1-2C语言程序设计进阶27例：全排列基本任务：产生N个自然数（1-N）的全排列N由命令行输入结果写在标准输出上输出结果按字典序排列2005-1-2C语言程序设计进阶28例：全排列(续)问题分析变元：自然数的个数N变元下限：1变元下限时的计算方法：直接输出当N大于1时：•第一个数字依次与其它数字交换，并在每次交换后对后N-1个数字进行全排列2005-1-2C语言程序设计进阶29例：全排列(续)程序实现要点：第一个数字首先与自身交换，以简化程序每次完成对后N-1个数字的全排列后，再进行同样的交换，以恢复交换前的状态，为下一次交换做准备数据结构要点包含N个元素的一维数组初始化：前N个自然数顺序放入数组的N个元素2005-1-2C语言程序设计进阶30例：全排列(续)程序结构#includestdio.h#includestdlib.h#defineMAXNUM16intmain(intc,char**v){intr[MAXNUM],i,n;n=atoi(v[1]);for(i=0;in;i++)r[i]=i+1;permu(r,0,n-1);}全排列函数：voidpermu(int*r,intk,intm)//r:操作对象数组,k:数组中参与全排列元素的起始位置,m:终止位置{inti;if(k==m){/*递归终止条件*/output(r,m);return;}for(i=k;i=m;i++){/*问题：为什么i=kswap(&r[k],&r[i]);permu(r,k+1,m);swap(&r[k],&r[i]);}}辅助函数：voidswap(int*a,int*b){inttmp=*a;*a=*b;*b=tmp;}voidoutput(int*list,intn){inti;for(i=0;i=n;i++)printf(%d,list[i]);putchar('\n');}2005-1-2C语言程序设计进阶33例：全排列(续)结果正确，基本符合要求输出结果未排序例：permu(3)123132213231321312原因数字交换后其后的n-1个数不一定是递增排列的2005-1-2C语言程序设计进阶34例：全排列(续)解决方法数字交换后保证其后的n-1个数递增排列实现方法1数字交换后对其后的n-1个数排序优点：易于想到缺点：不易恢复原状，需另行存储2005-1-2C语言程序设计进阶35例：全排列(续)实现方法2第k+1到i个数循环移位排序：向右循环移位恢复：向左循环移位例：12345-42315-4123512345-52341-51234缺点：思路稍微复杂一些优点实现简单，便于恢复原状，不需单独存储对原算法影响小排序版本的permu()：voidpermu(int*r,intk,intm){inti;if(k==m){output(r,m);return;}for(i=k;i=m;i++){swap(&r[k],&r[i]);circle_right(r,k+1,i);permu(r,k+1,m);circle_left(r,k+1,i);swap(&r[k],&r[i]);}}循环移位函数：voidcircular_right(int*r,intleft,intright){inttmp