《递归和递推课件》由会员分享，可在线阅读，更多相关《递归和递推课件（26页珍藏版）》请在金锄头文库上搜索。
1、递归和递推,陈旭龙,函数定义,递归的概念,一个函数、过程、概念或数据结构，如果在其定义或说明内部直接或间接地出现有其本身的引用，或者是为了描述问题的某一状态，必须用到它的上一状态，而描述上一状态，又必须用到它的上一状态这种用自己来定义的方法，称之为递归或者递归定义。 在程序设计中，过程或函数直接或者间接调用自己，就称为递归调用,递归过程实际上借助于一个递归工作栈来实现的。 首先问题向一个方向一步一步分解，既问题规模逐渐降低，这样，问题向一极推进的过程称之为递归过程； 然后这些问题又按后提出先解决的顺序依次得到解决，最后得到原问题的解。这样，在子问题得到逐一解决的基础上，最后回到原问题的解的变化
2、过程，称之为回归过程。,递归定义的要素,1、递归边界或终止条件。 2、递归定义，使问题向边界条件转化的规则。,var n:integer; function fibonacci(x:integer):integer; begin if (x=0) or (x=1) then exit(1); exit(fibonacci(x-1)+fibonacci(x-2); end; begin readln(n); writeln(fibonacci(n); end.,递归函数的应用,P1294 走楼梯 P1024 数字的根,递归的应用分析,P1293移梵塔 P1750 分形 P1752 红与黑,集合的
3、划分,设是一个具有n个元素的集合，a1，a2，an，现将划分成K个满足下列条件的子集合s1，s2，sk ，且满足： 1si 2sisj (1i，jk ij) 3s1s2s3sk 则称s1，s2，sk是集合的一个划分。它相当于把集合中的n个元素a1 ，a2，an 放入k个（0kn30）无标号的盒子中，使得没有一个盒子为空。请你确定n个元素a1 ，a2 ，an 放入k个无标号盒子中去的划分数s(n，k)。,先举个例子，设S1，2，3，4，k3，不难得出有6种不同的划分方案，即划分数s(4，3)=6，具体方案为： 1，234 1，324 1，423 2，314 2，413 3，412,考虑一般情况，
4、对于任意的含有n个元素a1 ，a2，an的集合s，放入k个无标号的盒子中去，划分数为s(n，k)，我们很难凭直觉和经验计算划分数和枚举划分的所有方案，必须归纳出问题的本质。 下面考虑对任一个元素an，则必然出现以下两种情况： 1、an是k个子集中的一个，于是我们只要把a1，a2，an-1 划分为k1子集，便解决了本题，这种情况下的划分数共有s(n1，k1)个； 2、an不是k个子集中的一个，则an必与其它的元素构成一个子集。则问题相当于先把a1，a2，an-1 划分成k个子集，这种情况下划分数共有(n1，k)个；然后再把元素an加入到k个子集中的任一个中去，共有k种加入方式，这样对于an的每一
5、种加入方式，都可以使集合划分为k个子集，因此根据乘法原理，划分数共有k*(n1，k)个。,综合上述两种情况，应用加法原理，得出n个元素的集合a1，a2，an划分为k个子集的划分数为以下递归公式： (n，k)(n1，k1)+k*s(n1，k) (nk，k0)。,确定s(n，k)的边界条件,首先不能把n个元素不放进任何一个集合中去，即k=0时，(n，k)0； 也不可能在不允许空盒的情况下把n个元素放进多于n的k个集合中去，即kn时,(n，k)0； 再者，把n个元素放进一个集合或把n个元素放进n个集合，方案数显然都是1，即k=1或k=n时，s(n,k)=1。 可以得出划分数(n，k)的递归关系式为：
6、 s(n，k)s(n1，k1)+k*s(n1，k) (nk，k0) s(n，k)0 (nk)或(k0) s(n，k)1 (k=1)或(kn),问题转变,P1456 盒子与球 P1295 装信,简单的背包问题,设有一个背包，可以放入的重量为S，现有n件物品，重量分别为t1，t2，ti，tn，均为正整数。从n件物品中挑选若干件，使得放入背包的重量之和正好为S。 样例输入： 10 5 1 6 2 7 5 样例输出： True,var s,n,i:integer; a:array1.100 of integer; function packge(s,n:integer):boolean; begin
7、if (n=1) and (san) then exit(false);边界 if s=an then exit(true); if ans then exit(packge(s,n-1); if san then begin if packge(s-an,n-1) then exit(true) else exit(packge(s,n-1); end; end; begin readln(s,n); for i:=1 to n do read(ai); writeln(packge(s,n); end.,P1409 装箱问题 P1180 可爱迷人的香穗子,递归与非递归的转化,在递归调用的过
8、程中，由于要保留每次调用时的参数和局部变量，而且要经过逐层调用和逐层返回两大过程，程序对于时间和存储空间的耗费可以说是巨大的。因此，在一个问题对于时空要求较高的情况下，有时不得不将递归方法转化成非递归方法，这一过程，常常称之为消除递归。消除递归的过程，其本质上就是要求模拟复杂的递归工作栈的变化过程，虽然递归与非递归在形式上大多能够相互转化，但是，非递归的编程难度要远远高于递归的方法,递推,在问题类型中，每个数据项都和它前面的若干个数据项（或后面的若干个数据项）有一定的关联，这种关联一般是通过一个递推关系式来表示的。求解问题时就从初始的一个或若干个数据项出发，通过递推关系式逐步推进，从而得到最终
9、结果。这种求解法就叫递推法,var a:array0.100 of longint; i:integer; begin readln(n); a0:=1; a1:=1; for i:=2 to n do ai:=ai-1+ai-2; writeln(an); end.,var n:integer; function fibonacci(x:integer):integer; begin if (x=0) or (x=1) then exit(1); exit(fibonacci(x-1)+fibonacci(x-2); end; begin readln(n); writeln(fibonac
10、ci(n); end.,算法框架,1、确定求解初始条件 2、求出递推公式 3、从边界出发进行顺推或倒推 4、输出结果,P1287 马拦过河卒,棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。棋盘用坐标表示，A点(0, 0)、B点(n, m)(n, m为不超过15的整数)，同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。,递归转化为递推,P1059 Hanoi双塔问题（NOIP2007普及组） P1023 递归函数 P1180 可爱迷人的香穗子,凸多边形的三角形剖分,在一个凸多边形中，通过若干条互不相交的对角线，把这个多边形剖分成了若干个三角形。现在的任务是从键盘输入凸多边形的边数n，求不同剖分的方案数Cn。比如当n=5时，有如下5中不同的方案，所以C5=5。,Catalan数列,练习,P1136 FBI序列,
