递推与递归课件

递推

有些问题中，相邻两项或多项数字（或状态）之间存在某种关系，可以通过前一项或多项按照某一规律推出其后一项数字（或状态），或者是通过后一项或多项按照某一规律推出其前一项数字（或状态）。我们可将这种规律归纳成如下递推关系式：Fn=g(Fn-1)或者Fn-1=g＇(Fn)递推有些问题中，相邻两项或多项数字（或状态）之间存在某递推已知初始值F1，通过递推关系式Fn=g(Fn-1)求出最终结果Fn的递推方式称为顺推法；同理，把已知最终结果为Fn，通过递推关系式Fn-1=g＇(Fn)求出初始值F1的递推方式称为倒推法。递推已知初始值F1，通过递推关系式Fn=g(Fn-1)求递推Fibonacci数列：Hn=Hn-1+Hn-2Fibonacci数列大家都非常熟悉，来源于中世纪数学家Fibonacci提出的一个问题：一对刚出生的兔子过两个月后,可以繁殖一对新兔子,问原有雌雄各一只兔子，经过十一个月后，能繁殖多少只兔子。递推Fibonacci数列：Hn=Hn-1+Hn递推【例题1】同一平面内有n（n≤500）条直线，已知其中p（p≥2）条直线相交于同一点，则这n条直线最多能将平面分割成多少个不同的区域？递推【例题1】递推【问题分析】由于共点直线的特殊性，我们决定先考虑p条相交于一点的直线，然后再考虑剩下的n-p条直线。首先可以直接求出，p条相交于一点的直线将平面划分成的区域数为2p个；然后在平面上已经有k（k≥p）条直线的基础上，再加上一条直线，最多可以与k条直线相交，而每次相交都会增加一个区域，与最后一条直线相交后，由于直线可以无限延伸，还会再增加一个区域。所以fi=fi-1+i（i＞p），边界条件在前面已经计算过了，是fp=2p。递推【问题分析】递推

f(p)=2*pf(i)=f(i-1)+i(i>p)递推递推programex1;varn,p,total,i:longint;beginreadln(n,p);total:=2*p;fori:=p+1tondototal:=total+i;writeln(total);end.递推programex1;递推【例题2】（NOIP2002初中组第4题）棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下或向右。同时在棋盘上的任一点有一个对方的马（如图的C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。卒不能走到对方马的控制点。递推【例题2】（NOIP2002初中组第4题）一个对方的递推棋盘用坐标表示，A点坐标（0,0）、B点坐标（n,m）（n，m为不超过20的整数，并由键盘输入），同样马的位置坐标C是需要给出的（C≠A且C≠B），现在从键盘输入B点的坐标（n,m）以及对方马的坐标（x,y），要求你计算出卒从A点能够到达B点的路径条数。递推棋盘用坐标表示，A点坐标（0,0）、B点坐标（n,m递推【问题分析】在学习回溯或搜索时，跳马是一道典型的例题，有些同学在比赛时用了搜索，但事实证明：当n，m=15就会超时。其实，对本题稍加分析就能发现，要到达棋盘上的一个点，只能从左边过来（称之为左点）或是从上面过来（称之为上点）。递推【问题分析】递推根据加法原理，到达某一点的路径数目，就等于到达其相邻的上点和左点的路径数目之和，因此我们可以使用逐行（或逐列）递推的方法来求出从起点到终点的路径数目。障碍点（马的控制点）也完全适用，只要将到达该点的路径数目设置为0即可。递推根据加法原理，到达某一点的路径数目，就等于到达其相邻递推假设用F[i,j]表示到达点（i,j）的路径数目，用g[i,j]表示点（i,j）是否是对方马的控制点，g[i,j]=0表示不是对方马的控制点，g[i,j]=1表示是对方马的控制点。则可得到如下的递推关系式：

F[i,j]=0 {g[i,j]=1} F[0,j]=F[0,j-1]{j>0，g[0,j]=0}F[i,0]=F[i-1,0] {i>0，g[i,0]=0}F[i,j]=F[i-1,j]+F[i,j-1]{i>0，j>0，g[i,j]=0}递推假设用F[i,j]表示到达点（i,j）的路径数目，用递推programex2;constmaxn=20;maxm=20;dx:array[1..8]ofinteger=(2,1,-1,-2,-2,-1,1,2);dy:array[1..8]ofinteger=(1,2,2,1,-1,-2,-2,-1);varf:array[0..maxn,0..maxm]ofint64;g:array[-2..maxn+2,-2..maxm+2]ofboolean;n,m,x,y:integer;i,j:integer;递推programex2;递推beginreadln(n,m,x,y);fillchar(f,sizeof(f),0);fillchar(g,sizeof(g),true);g[x,y]:=false;fori:=1to8dog[x+dx[i],y+dy[i]]:=false;递推begin递推ifg[0,0]thenf[0,0]:=1;fori:=1tomdoifg[0,i]thenf[0,i]:=f[0,i-1];fori:=1tondoifg[i,0]thenf[i,0]:=f[i-1,0];fori:=1tondoforj:=1tomdoifg[i,j]thenf[i,j]:=f[i-1,j]+f[i,j-1];writeln(f[n,m]);递推ifg[0,0]thenf[0,0]:=1;递推

【例题3】特殊的子集 集合M={1,2,3,……n}的子集中，有一些是不含相邻自然数元素的。例如：n=4时，集合{1,3}是满足要求的，而{1,3,4}是不满足的，因为它含有相邻自然数3和4。把所有满足要求的子集记作Si，对于每一个Si计算出它的所有元素的乘积Ti，求∑Ti2。

输入 仅一行，包括一个正整数n(n≤100)

输出 仅一行，即Ti的平方和，可能会超出长整型范围。递推 【例题3】特殊的子集递推样例输入：4样例输出：119{1,2,3,4}中符合题目要求的子集有：{1},{2},{3},{4},{1,3},{1,4},{2,4}12+22+32+42+(1*3)2+(1*4)2+(2*4)2=1+4+9+16+9+16+64=119递推样例输入：递推{1,2,3}的情况：{1},{2},{3},{1,3}－－－＞f(3){1,2,3,4}的情况：{1},{2},{3},{4},{1,3},{1,4},{2,4}－－－＞f(4){1,2,3,4,5}的情况：{1},{2},{3},{4},{5},{1,3},{1,4},{1,5},{2,4},{2,5},{3,5},{1,3,5}－－－＞f(5)f(5)=f(4)+f(3)*52+52f(i)=f(i-1)+f(i-2)*i2+i2递推{1,2,3}的情况：f(5)=f(4)+f(3)*递推f(1)=12=1f(2)=12+22=5f(3)=f(2)+f(1)*32+32=23f(4)=f(3)+f(2)*42+42=119………f(n)=f(n-1)+f(n-2)*n2+n22!-13!-14!-15!-1………(n+1)!-1递推f(1)=12=12!-1递推【讨论1】平面分割问题设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。递推【讨论1】平面分割问题递推【讨论2】Catalan数在一个凸n边形中，通过不相交于的n边形内部的对角线，把n边形拆分成若干三角形。拆分方法的数目用hn表示，hn即为Catalan数。例如，五边形有如下五种拆分方案，故h5=5。求一个任意的凸n边形相应的hn。递推【讨论2】Catalan数递归递归算法 设一个未知函数f，用其自身构成的已知函数g来定义： f(n)=g(n,f(n-1))n>0 f(0)=an=0 则称函数f为递归函数（递归公式），为了求f(n)，我们必须先求f(n-1)，为了求f(n-1),又必须去求f(n-2)，……，为了求f(1),必须先求f(0),而f(0)是已知的。这种定义函数的方式称为递归定义。递归递归算法递归一个递归定义必须是有确切含义的，也就是说一步比一步简单，最终是有终结的，决不能无限循环下去。比如上例中的f(0)=a，这种最简单的情况（终结条件），称为递归边界，它是递归定义必不可少的一部分。描述递归定义的函数或求解递归问题的过程称为递归算法。递归一个递归定义必须是有确切含义的，也就是说一步比一步简递归不论是递归过程，还是递归函数，按其调用的方式一般分为直接递归（子程序P直接调用自己）和间接递归（子程序P调用其它子程序，其它子程序又调用P）。递归不论是递归过程，还是递归函数，按其调用的方式一般分为递归递归算法一般适用在三个场合： 一是数据的定义形式是递归的，如求Fibonacci数列问题； 二是数据之间的逻辑关系（即数据结构）是递归的，如树、图等的定义和操作； 三是某些问题虽然没有明显的递归关系或结构，但问题的解法是不断重复执行一种操作，只是问题规模由大化小，直至某个原操作（基本操作）就结束，如汉诺塔问题，这种问题使用递归思想来求解比其它方法更简单。递归递归算法一般适用在三个场合：递归递归不仅可用于计算、计数，而且还可用于枚举，即把所有具有各某种特性的对象完全枚举出来，关键是如何从输入参数与输出结果之间的对应关系中归纳出递归公式和边界条件。递归递归不仅可用于计算、计数，而且还可用于枚举，即把所有递归的应用举例【例题4】集合的划分【问题描述】设ｓ是一个具有n个元素的集合，ｓ＝｛a1，a2，……，an｝，现将ｓ划分成K个满足下列条件的子集合s1，s2，……，sk，且满足： 1．si≠φ 2．si∩sj＝φ(1≤i，j≤ki≠j) 3．s1∪s2∪s3∪…∪sk＝ｓ 则称s1，s2，……，sk是集合ｓ的一个划分。它相当于把ｓ集合中的n个元素a1，a2，……，an

放入k个（0<k≤n<30）无标号的盒子中，使得没有一个盒子为空。请你确定n个元素a1，a2，……，an

放入k个无标号盒子中去的划分数s(n，k)。递归的应用举例【例题4】集合的划分递归的应用举例【问题分析】先举个例子，设S＝｛1，2，3，4｝，k＝3，不难得出ｓ有6种不同的划分方案，即划分数s(4，3)=6，具体方案为： ｛1，2｝∪｛3｝∪｛4｝ ｛1，3｝∪｛2｝∪｛4｝ ｛2，3｝∪｛1｝∪｛4｝ ｛1，4｝∪｛2｝∪｛3｝ ｛2，4｝∪｛1｝∪｛3｝ ｛3，4｝∪｛1｝∪｛2｝递归的应用举例【问题分析】先举个例子，设S＝｛1，2，3，4递归的应用举例 考虑一般情况，对于任意的含有n个元素a1，a2，……，an的集合s，放入k个无标号的盒子中去，划分数为s(n，k)，我们很难凭直觉和经验计算划分数和枚举划分的所有方案，必须归纳出问题的本质。下面考虑对任一个元素an，则必然出现以下两种情况： 1、｛an｝是k个子集中的一个，于是我们只要把a1，a2，……，an-1

划分为k－1子集，便解决了本题，这种情况下的划分数共有s(n－1，k－1)个；递归的应用举例 考虑一般情况，对于任意的含有n个元素a1递归的应用举例 2、｛an｝不是k个子集中的一个，则an必与其它的元素构成一个子集。则问题相当于先把a1，a2，……，an-1

划分成k个子集，这种情况下划分数共有ｓ(n－1，k)个；然后再把元素an加入到k个子集中的任一个中去，共有k种加入方式，这样对于an的每一种加入方式，都可以使集合划分为k个子集，因此根据乘法原理，划分数共有k*ｓ(n－1，k)个。递归的应用举例 2、｛an｝不是k个子集中的一个，则an必递归的应用举例综合上述两种情况，应用加法原理，得出n个元素的集合｛a1，a2，……，an｝划分为k个子集的划分数为以下递归公式：ｓ(n，k)＝ｓ(n－1，k－1)+k*s(n－1，k)(n>k，k>0)。递归的应用举例综合上述两种情况，应用加法原理，得出n个元素的递归的应用举例 确定s(n，k)的边界条件,首先不能把n个元素不放进任何一个集合中去，即k=0时，ｓ(n，k)＝0；也不可能在不允许空盒的情况下把n个元素放进多于n的k个集合中去，即k＞n时,ｓ(n，k)＝0；再者，把n个元素放进一个集合或把n个元素放进n个集合，方案数显然都是1，即k=1或k=n时，s(n,k)=1。 因此，我们可以得出划分数ｓ(n，k)的递归关系式为： s(n，k)＝s(n－1，k－1)+k*s(n－1，k)(n>k，k>0) s(n，k)＝0(n<k)或(k＝0) s(n，k)＝1(k=1)或(k＝n)递归的应用举例 确定s(n，k)的边界条件,首先不能把n个递归的应用举例【例题5】直线的交点数【问题描述】平面上有n条直线，且无三线共点，问这些直线能有多少种不同的交点数。【问题输入】n(n≤20)。【问题输出】若干行，列出所有相交方案，其中每一行为一个可能的交点数。递归的应用举例【例题5】直线的交点数递归的应用举例【样例输入】 4【样例输出】 0 3 4 5 6（表示4条直线的情况下，可能有0，3，4，5，6个交点）递归的应用举例【样例输入】递归的应用举例【问题分析】 我们将n条直线排成一个序列。直线2与直线1最多有一个交点；直线3与直线1和直线2最多有2个交点，……，直线n与其它n-1条直线最多有n-1个交点。由此得出n条直线互不平行且无三线共点的最多交点数max=1+2+…+(n-1)=n*(n-1)/2。但本题远远不只这么简单，因为问题是问：这些直线能有多少种不同的交点数？递归的应用举例【问题分析】递归的应用举例 设数组g[1..max],g[i]=0表示交点数i不存在,g[i]=1表示交点数i存在（0≤i≤max）。 容易列举出i=1，2，3的情形如图，下面我们来具体分析n=4的情况：递归的应用举例 设数组g[1..max],g[i]=0表示递归的应用举例1、四条直线全部平行，无交点，g[0]=12、其中三条直线平行，交点数为3*1+0=3，g[3]=13、其中二条直线平行。这两条直线与另外两条直线之间的交点数为2*2=4。而另外两条直线本身既可能平行亦可能相交，因此交点数分别为

(n-2)*2+0=4g[4]=1(n-2)*2+1=5g[5]=1递归的应用举例1、四条直线全部平行，无交点，g[0]=1递归的应用举例4、四条直线互不平行。交点数为1*3+3条直线的相交情况1*3+0=3g[3]=11*3+2=5g[5]=11*3+3=6g[6]=1递归的应用举例4、四条直线互不平行。交点数为1*3+3条直线递归的应用举例 即n=4时，有0个、3个、4个、5个、6个不同的交点数，所以有5种可能。从上述n=4的分析中，我们发现：m条直线的交点方案=(m-r)条平行线与r条直线交叉的交点数+r条直线本身的交点方案=(m-r)*r+r条直线本身的交点方案（1≤r≤m）递归的应用举例 即n=4时，有0个、3个、4个、5个、6个递归的应用举例上式说明，计算不同交点方案的问题是递归的，可以描述成如下递归算法：proceduretry(m，j){m为直线数，j为交点数}beginifm>0{若直线存在，则递归计算所有的交叉情况}

thenforr:=mdownto1dotry(m-r，j+r*(m-r))elseg[j]←1;{否则确定m条直线存在j个交点}end；递归的应用举例上式说明，计算不同交点方案的问题是递归的，可递归的应用举例1、计算max：max=n*(n-1)/2； {计算n条直线的最多交点数}2、初始化：fillchar(g，sizeof(g)，0)；3、递归求g[i]：try(n，0)；4、统计方案数并输出：

total：=0；fori：=0tomaxdoifg[i]=1thenbegintotal:=total+1；输出第total个方案的交点数i；end；递归的应用举例1、计算max：max=n*(n-1)/2；递推与递归的比较共同点：

1、数据元素可以用抽象的公式表示

2、具有边界条件不同点：

1、递推从边界出发求其结果

2、递归从问题自身出发达到边界递推与递归的比较共同点：递推

有些问题中，相邻两项或多项数字（或状态）之间存在某种关系，可以通过前一项或多项按照某一规律推出其后一项数字（或状态），或者是通过后一项或多项按照某一规律推出其前一项数字（或状态）。我们可将这种规律归纳成如下递推关系式：Fn=g(Fn-1)或者Fn-1=g＇(Fn)递推有些问题中，相邻两项或多项数字（或状态）之间存在某递推已知初始值F1，通过递推关系式Fn=g(Fn-1)求出最终结果Fn的递推方式称为顺推法；同理，把已知最终结果为Fn，通过递推关系式Fn-1=g＇(Fn)求出初始值F1的递推方式称为倒推法。递推已知初始值F1，通过递推关系式Fn=g(Fn-1)求递推Fibonacci数列：Hn=Hn-1+Hn-2Fibonacci数列大家都非常熟悉，来源于中世纪数学家Fibonacci提出的一个问题：一对刚出生的兔子过两个月后,可以繁殖一对新兔子,问原有雌雄各一只兔子，经过十一个月后，能繁殖多少只兔子。递推Fibonacci数列：Hn=Hn-1+Hn递推【例题1】同一平面内有n（n≤500）条直线，已知其中p（p≥2）条直线相交于同一点，则这n条直线最多能将平面分割成多少个不同的区域？递推【例题1】递推【问题分析】由于共点直线的特殊性，我们决定先考虑p条相交于一点的直线，然后再考虑剩下的n-p条直线。首先可以直接求出，p条相交于一点的直线将平面划分成的区域数为2p个；然后在平面上已经有k（k≥p）条直线的基础上，再加上一条直线，最多可以与k条直线相交，而每次相交都会增加一个区域，与最后一条直线相交后，由于直线可以无限延伸，还会再增加一个区域。所以fi=fi-1+i（i＞p），边界条件在前面已经计算过了，是fp=2p。递推【问题分析】递推

f(p)=2*pf(i)=f(i-1)+i(i>p)递推递推programex1;varn,p,total,i:longint;beginreadln(n,p);total:=2*p;fori:=p+1tondototal:=total+i;writeln(total);end.递推programex1;递推【例题2】（NOIP2002初中组第4题）棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下或向右。同时在棋盘上的任一点有一个对方的马（如图的C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。卒不能走到对方马的控制点。递推【例题2】（NOIP2002初中组第4题）一个对方的递推棋盘用坐标表示，A点坐标（0,0）、B点坐标（n,m）（n，m为不超过20的整数，并由键盘输入），同样马的位置坐标C是需要给出的（C≠A且C≠B），现在从键盘输入B点的坐标（n,m）以及对方马的坐标（x,y），要求你计算出卒从A点能够到达B点的路径条数。递推棋盘用坐标表示，A点坐标（0,0）、B点坐标（n,m递推【问题分析】在学习回溯或搜索时，跳马是一道典型的例题，有些同学在比赛时用了搜索，但事实证明：当n，m=15就会超时。其实，对本题稍加分析就能发现，要到达棋盘上的一个点，只能从左边过来（称之为左点）或是从上面过来（称之为上点）。递推【问题分析】递推根据加法原理，到达某一点的路径数目，就等于到达其相邻的上点和左点的路径数目之和，因此我们可以使用逐行（或逐列）递推的方法来求出从起点到终点的路径数目。障碍点（马的控制点）也完全适用，只要将到达该点的路径数目设置为0即可。递推根据加法原理，到达某一点的路径数目，就等于到达其相邻递推假设用F[i,j]表示到达点（i,j）的路径数目，用g[i,j]表示点（i,j）是否是对方马的控制点，g[i,j]=0表示不是对方马的控制点，g[i,j]=1表示是对方马的控制点。则可得到如下的递推关系式：

F[i,j]=0 {g[i,j]=1} F[0,j]=F[0,j-1]{j>0，g[0,j]=0}F[i,0]=F[i-1,0] {i>0，g[i,0]=0}F[i,j]=F[i-1,j]+F[i,j-1]{i>0，j>0，g[i,j]=0}递推假设用F[i,j]表示到达点（i,j）的路径数目，用递推programex2;constmaxn=20;maxm=20;dx:array[1..8]ofinteger=(2,1,-1,-2,-2,-1,1,2);dy:array[1..8]ofinteger=(1,2,2,1,-1,-2,-2,-1);varf:array[0..maxn,0..maxm]ofint64;g:array[-2..maxn+2,-2..maxm+2]ofboolean;n,m,x,y:integer;i,j:integer;递推programex2;递推beginreadln(n,m,x,y);fillchar(f,sizeof(f),0);fillchar(g,sizeof(g),true);g[x,y]:=false;fori:=1to8dog[x+dx[i],y+dy[i]]:=false;递推begin递推ifg[0,0]thenf[0,0]:=1;fori:=1tomdoifg[0,i]thenf[0,i]:=f[0,i-1];fori:=1tondoifg[i,0]thenf[i,0]:=f[i-1,0];fori:=1tondoforj:=1tomdoifg[i,j]thenf[i,j]:=f[i-1,j]+f[i,j-1];writeln(f[n,m]);递推ifg[0,0]thenf[0,0]:=1;递推

【例题3】特殊的子集 集合M={1,2,3,……n}的子集中，有一些是不含相邻自然数元素的。例如：n=4时，集合{1,3}是满足要求的，而{1,3,4}是不满足的，因为它含有相邻自然数3和4。把所有满足要求的子集记作Si，对于每一个Si计算出它的所有元素的乘积Ti，求∑Ti2。

输入 仅一行，包括一个正整数n(n≤100)

输出 仅一行，即Ti的平方和，可能会超出长整型范围。递推 【例题3】特殊的子集递推样例输入：4样例输出：119{1,2,3,4}中符合题目要求的子集有：{1},{2},{3},{4},{1,3},{1,4},{2,4}12+22+32+42+(1*3)2+(1*4)2+(2*4)2=1+4+9+16+9+16+64=119递推样例输入：递推{1,2,3}的情况：{1},{2},{3},{1,3}－－－＞f(3){1,2,3,4}的情况：{1},{2},{3},{4},{1,3},{1,4},{2,4}－－－＞f(4){1,2,3,4,5}的情况：{1},{2},{3},{4},{5},{1,3},{1,4},{1,5},{2,4},{2,5},{3,5},{1,3,5}－－－＞f(5)f(5)=f(4)+f(3)*52+52f(i)=f(i-1)+f(i-2)*i2+i2递推{1,2,3}的情况：f(5)=f(4)+f(3)*递推f(1)=12=1f(2)=12+22=5f(3)=f(2)+f(1)*32+32=23f(4)=f(3)+f(2)*42+42=119………f(n)=f(n-1)+f(n-2)*n2+n22!-13!-14!-15!-1………(n+1)!-1递推f(1)=12=12!-1递推【讨论1】平面分割问题设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。递推【讨论1】平面分割问题递推【讨论2】Catalan数在一个凸n边形中，通过不相交于的n边形内部的对角线，把n边形拆分成若干三角形。拆分方法的数目用hn表示，hn即为Catalan数。例如，五边形有如下五种拆分方案，故h5=5。求一个任意的凸n边形相应的hn。递推【讨论2】Catalan数递归递归算法 设一个未知函数f，用其自身构成的已知函数g来定义： f(n)=g(n,f(n-1))n>0 f(0)=an=0 则称函数f为递归函数（递归公式），为了求f(n)，我们必须先求f(n-1)，为了求f(n-1),又必须去求f(n-2)，……，为了求f(1),必须先求f(0),而f(0)是已知的。这种定义函数的方式称为递归定义。递归递归算法递归一个递归定义必须是有确切含义的，也就是说一步比一步简单，最终是有终结的，决不能无限循环下去。比如上例中的f(0)=a，这种最简单的情况（终结条件），称为递归边界，它是递归定义必不可少的一部分。描述递归定义的函数或求解递归问题的过程称为递归算法。递归一个递归定义必须是有确切含义的，也就是说一步比一步简递归不论是递归过程，还是递归函数，按其调用的方式一般分为直接递归（子程序P直接调用自己）和间接递归（子程序P调用其它子程序，其它子程序又调用P）。递归不论是递归过程，还是递归函数，按其调用的方式一般分为递归递归算法一般适用在三个场合： 一是数据的定义形式是递归的，如求Fibonacci数列问题； 二是数据之间的逻辑关系（即数据结构）是递归的，如树、图等的定义和操作； 三是某些问题虽然没有明显的递归关系或结构，但问题的解法是不断重复执行一种操作，只是问题规模由大化小，直至某个原操作（基本操作）就结束，如汉诺塔问题，这种问题使用递归思想来求解比其它方法更简单。递归递归算法一般适用在三个场合：递归递归不仅可用于计算、计数，而且还可用于枚举，即把所有具有各某种特性的对象完全枚举出来，关键是如何从输入参数与输出结果之间的对应关系中归纳出递归公式和边界条件。递归递归不仅可用于计算、计数，而且还可用于枚举，即把所有递归的应用举例【例题4】集合的划分【问题描述】设ｓ是一个具有n个元素的集合，ｓ＝｛a1，a2，……，an｝，现将ｓ划分成K个满足下列条件的子集合s1，s2，……，sk，且满足： 1．si≠φ 2．si∩sj＝φ(1≤i，j≤ki≠j) 3．s1∪s2∪s3∪…∪sk＝ｓ 则称s1，s2，……，sk是集合ｓ的一个划分。它相当于把ｓ集合中的n个元素a1，a2，……，an

放入k个（0<k≤n<30）无标号的盒子中，使得没有一个盒子为空。请你确定n个元素a1，a2，……，an

放入k个无标号盒子中去的划分数s(n，k)。递归的应用举例【例题4】集合的划分递归的应用举例【问题分析】先举个例子，设S＝｛1，2，3，4｝，k＝3，不难得出ｓ有6种不同的划分方案，即划分数s(4，3)=6，具体方案为： ｛1，2｝∪｛3｝∪｛4｝ ｛1，3｝∪｛2｝∪｛4｝ ｛2，3｝∪｛1｝∪｛4｝ ｛1，4｝∪｛2｝∪｛3｝ ｛2，4｝∪｛1｝∪｛3｝ ｛3，4｝∪｛1｝∪｛2｝递归的应用举例【问题分析】先举个例子，设S＝｛1，2，3，4递归的应用举例 考虑一般情况，对于任意的含有n个元素a1，a2，……，an的集合s，放入k个无标号的盒子中去，划分数为s(n，k)，我们很难凭直觉和经验计算划分数和枚举划分的所有方案，必须归纳出问题的本质。下面考虑对任一个元素an，则必然出现以下两种情况： 1、｛an｝是k个子集中的一个，于是我们只要把a1，a2，……，an-1

划分为k－1子集，便解决了本题，这种情况下的划分数共有s(n－1，k－1)个；递归的应用举例 考虑一般情况，对于任意的含有n个元素a1递归的应用举例 2、｛an｝不是k个子集中的一个，则an必与其它的元素构成一个子集。则问题相当于先把a1，a2，……，an-1

划分成k个子集，这种情况下划分数共有ｓ(n－1，k)个；然后再把元素an加入到k个子集中的任一个中去，共有k种加入方式，这样对于an的每一种加入方式，都可以使集合划分为k个子集，因此根据乘法原理，划分数共有k*ｓ(n－1，k)个。递归的应用举例 2、｛an｝不是k个子集中的一个，则an必递归的应用举例综合上述两种情况，应用加法原理，得出n个元素的集合｛a1，a2，……，an｝划分为k个子集的划分数为以下递归公式：ｓ(n，k)＝ｓ(n－1，k－1)+k*s(n－1，k)(n>k，k>0)。递归的应用举例综合上述两种情况，应用加法原理，得出n个元素的递归的应用举例 确定s(n，k)的边界条件,首先不能把n个元素不放进任何一个集合中去，即k=0时，ｓ(n，k)＝0；也不可能在不允许空盒的情况下把n个元素放进多于n的k个集合中去，即k＞n时,ｓ(n，k)＝0；再者，把n个元素放进一个集合或把n个元素放进n个集合，方案数显然都是1，即k=1或k=n时，s(n,k)=1。 因此，我们可以得出划分数ｓ(n，k)的递归关系式为： s(n，k)＝s(n－1，k－1)+k*s(n－1，k)(n>k，k>0) s(n，k)＝0(n<k)或(k＝0) s(n，k)＝1(k=1)或(k＝n)递归的应用举例 确定s(n，k)的边界条件,首先不能把n个递归的应用举例【例题5】直线的交点数【问题描述】平面上有n条直线，且无三线共点，问这些直线能有多少种不同的交点数。【问题输入】n(n≤20)。【问题输出】若干行，列出所有相交方案，其中每一行为一个可能的交点数。递归的应用举例【例题5】直线的交点数递归的应用举例【样例输入】 4【样例输出】 0 3 4 5 6（表示4条直