第5章 递归

第5章递归学习目标:理解递归的概念。掌握用分治法设计有效算法的策略。掌握用动态规划法设计有效算法的策略。掌握用回朔法解题的算法设计策略。理解递归算法的工作原理和模拟递归的方法。5.1递归的概念直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。递归定义举例：祖先、二叉树等。递归应用举例：数学归纳法等递归应用举例阶乘函数intfactorial(intn){if(n==0)return1;returnn*factorial(n-1);}Fibonacci数列intfibonacci(intn){if(n=1)return1;returnfibonacci(n-1)+fibonacci(n-2)}递归应用举例Ackerman函数A(1,0)=2;A(0,m)=1;A(n,0)=n+2;A(n,m)=A(A(n-1,m),m-1)N个元素全排列voidperm(intlist[],intk,intm){inti;if(k==m){for(i=0;i=m;i++)printf(“%d”,list[i]);printf(“\n”);}else{for(i=k;i=m;i++){swap(list[k],list[i]);perm(list,k+1,m);swap(list[k],list[i]);}}}递归应用举例整数划分问题intq(intn,intm){if((n1)||(m1))return0;if((n==1)||(m==1))return1;if(nm)returnq(n,n);if(n==m)returnq(n,m-1)+1;returnq(n,m-1)+q(n-m,m);}递归应用举例链表结构intListLength(ListL){returncount(L-first);}intcount(linkx){if(x==0)return0;return1+count(x-next);}递归应用举例间接递归sin2θ=2sinθcosθcos2θ=1-2*sinθ*sinθdoubles(doublex){if(-0.005x&&x0.005)returnx-x*x*x/6;return2*s(x/2)*c(x/2);}doublec(doublex){if(-0.005x&&x0.005)return1.0-x*x/2;return1.0-2*s(x/2)*s(x/2);}5.2.1分治与递归分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。分治法的设计模式：divide-and-conquer(P){if(|P|=n0)adhoc(P);dividePintosmallersubinstancesP1,P2…Pk;for(i=1;i=k;i++)yi=divide-and-conquer(Pi);returnmerge(y1,…,yk);}5.2.1分治法应用举例二分搜索技术二分搜索算法的基本思想是将n个元素分成个数大致相同的两半，取a[n/2]与x进行比较。如果x=a[n/2]，则找到x,算法终止。如果xa[n/2],则只要在数组a的左半部继续搜索x。如果xa[n/2],则只要在数组a的右半部继续搜索x。棋盘覆盖问题：合并排序：将待排序元素分成大小大致相同的2个子集合，分别对2个子集进行排序，最终将排好序的子集合合并成为所要求的集合。快速排序线性时间选择：给定线性序集中n个元素和一个整数k,1=k=n,要求找出这n个元素中第k小的元素，即当k=1时找的是最小元素，k=n时找的是最大元素，当k=(n+1)/2时，成为找中位数。5.2.1分治法应用举例最接近点对问题给定平面上n个点，找其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最少。循环赛日程表问题5.2.2动态规划动态规划算法适用于解最优化问题。通常可以按以下步骤设计：找出最优解的性质，并刻画其结构特征；递归地定义最优值；以自底向上的方式计算出最优值；根据计算最优值时得到的信息，构造最优解。5.2.2动态规划动态规划算法的基本要素最优子结构；重叠子问题；备忘录方法；5.2.2动态规划举例矩阵连乘问题；最长公共子序列；给定两个序列X和Y,找出X和Y的公共最长子序列给定两个序列X,Y,当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。例如，若X={A,B,C,B,D,A,B}Y={B,D,C,A,B,A}则序列{B,C,A}是X,Y的公共子序列。而序列{B,C,B,Z}是X,Y的最长公共子序列。5.2.2动态规划举例凸多边形最优三角剖分给定凸多边形P={V0,V1…Vn-1},以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分，使得该三角剖分所对应的权，即该三角剖分中诸三角形上权之和为最少。5.2.2动态规划举例图像压缩电路布线流水作业调度0-1背包问题给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的容量为C。问：应该如何选择装入背包的物品，使得装入背包中物品的总价值最大。5.2.3回溯与递归回溯法有“通用解题法”之称。用它可以系统地搜索问题的所有解。回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。回溯法求问题的一个解时，只要搜索到问题的一个解就可结束。这种以深度优先方式系统搜索问题解的算法称为回溯法，它适用于求解组合数较大的问题。其他算法贪心算法分支定界法概率算法近似算法等