[小学教育]第5章递归.pptVIP

第 5 章 递归 授课班级：可视化、数据库 学习目标 理解递归的概念 掌握用分治法设计有效算法的策略 掌握用动态规划方法设计有效算法的策略 掌握回溯法解题的算法设计策略 理解递归算法的工作原理 5.1 递归的概念 定义：一个算法中，若其中有调用自身（直接或间接）的过程，则该算法就是一个递归算法，简称递归。（自调用） 注意：递归算法必须是逐步有规律简化的，最终要有一个非递归的出口，不能出现无穷调用的情况。 在计算机科学中，递归的思想主要表现在三个方面： 数据的定义形式是递归的 数据的结构形式是递归的 问题的解法是递归的 递归算法的基本思想是：把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。规模较小的问题又变成规模更小的问题，并且小到一定程度可以直接得出它的解，从而得到原来问题的解。 利用递归算法解题，首先要对问题的以下三个方面进行分析： 决定问题规模的参数。需要用递归算法解决的问题，其规模通常都是比较大的，在问题中决定规模大小（或问题复杂程度）的量有哪些？ 问题的边界条件及边界值。在什么情况下可以直接得出问题的解？这就是问题的边界条件及边界值。 解决问题的通式。把规模大的、较难解决的问题变成规模较小、易解决的同一问题，需要通过哪些步骤或等式来实现？这是解决递归问题的难点。把这些步骤或等式确定下来。 实例 定义是递归的情况 例1：阶乘函数 写成递归算法如下： int Factorial ( int n ) { if ( n = = 0 ) return 1； else return n*Factorial (n-1)； } 例2：Fibonacci数列 无穷数列1，1，2，3，5，8，13，21，34，55，……称为Fibonacci数列 描述如下： int fibonacci ( int n ) { if ( n = 1 ) return 1; else return fibonacci (n-1) + fibonacci (n-2); } 双递归函数：当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。 例3：Ackerman函数 A(n,m)的自变量m的每一个值都定义了一个单变量函数。 m =1时，A(n,1)=2n (n=1); m =2时，A(n,2)=2n ; m =3时，A(n,3)=22. .2 (其中指数中2的层数为n); …… 推导： 例4：排列问题 设R={r1,r2,… …rn}是要进行排列的n个元素，Ri=R-{ri}。R的全排列可归纳定义为： 当n=1时，perm(R)=(r),其中r是集合R中唯 一的元素； 当n1时， perm(R)由(r1) perm(R1), (r2) perm(R2), … … ,(rn) perm(Rn) 构成。 全排列的递归算法如下： void perm (int list[ ],int k,int m) { int i; 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]); } } 例5：整数划分问题 将一个正整数n表示成形如下式的一系列正整数的和，称为n的一个分划。 n＝n1＋n2＋……＋nk (ni≥1，i＝1,2,……,k,k≥1) 且n≥n1≥n2≥……≥nk ≥1 正整数n的不同的划分个数称为正整数n的划分数，记作p(n)。 例如：整数6的分划数有11种: 6； 5+1； 4+2，4+1+1； 3+3，3+2+1，3+1+1+1； 2+2+2，2+2+1+1，2+1+1+1+1； 1+1+1+1+1+1； 在正整数n的所有不同的划分中，将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系： (1) q(n,1)=1, n≥1 (2) q