第10周递归与递推数论基础

1、递推和递归递 推 有些问题中，相邻两项或多项数字（或状态）之间存在某种关系，可以通过前一项或多项按照某一规律推出其后一项数字（或状态），或者是通过后一项或多项按照某一规律推出其前一项数字（或状态）。我们可将这种规律归纳成如下递推关系式：Fn=g(Fn-1)或者Fn-1=g(Fn)递 推已知初始值F1，通过递推关系式Fn=g(Fn-1)求出最终结果Fn的递推方式称为顺推法；同理，把已知最终结果为Fn，通过递推关系式Fn-1=g(Fn)求出初始值F1的递推方式称为倒推法。递 推Fibonacci数列：Hn = Hn-1 + Hn-2Fibonacci数列大家都非常熟悉，来源于中世纪数学家Fibon

2、acci提出的一个问题：一对刚出生的兔子过两个月后,可以繁殖一对新兔子,问原有雌雄各一只兔子，经过十一个月后，能繁殖多少只兔子。递 推【例题1】平面分割在一个平面上有一个圆和n条直线，这些直线中每一条在圆内同其他直线相交，假设没有3条直线相交于一点，试问这些直线将圆分成多少区域。递 推【问题分析】F(1)=2; F(n) = F(n-1)+n;第n根线段被分为n段化简后：F(n) = n(n+1)/2 +1;递 推【引申：折线分割平面】问题描述 平面上有n条折线，问这些折线最多能将平面分割成多少块?样例输入 样例输出1 22 7递 推【引申：折线分割平面】第n根折线被分为2*2(n-1)段结论

3、F(n)=F(n-1)+4(n-1)+1递 推【思考题：平面分割方法】问题的提出： 设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。2022/10/610F(1)=2F(n)=F(n-1)+2(n-1)简单分析递 推2022/10/611【例2：错排问题】某人写了n封信和n个信封，如果所有的信都装错了信封。求所有的信都装错信封,共有多少种不同情况。 递 推2022/10/6121、当N=1和2时，易得解，假设F(N-1)和F(N-2)已经得到，重点分析下面的情况：4、后者简单，只能是没装错的那封和第N封交换信

4、封，没装错的那封可以是前面N-1封中的任意一个，故= F(N-2) * (N-1)3、前者，对于每种错装，可从N-1封信中任意取一封和第N封错装，故=F(N-1)*(N-1)2、当有N封信的时候，前面N-1封信可以有N-1或者 N-2封错装(为什么要考虑N-2?)递 推2022/10/613【例3：填充问题】在2n的长方形方格中,用n个12的骨牌铺满方格,例如n=3时,为23方格，骨牌的铺放方案有三种(如图), 输入n ,输出铺放方案的总数递 推2022/10/614【例3的延伸】有1n的一个长方形，用11、12、13的骨牌铺满方格。例如当n=3时为13的方格（如图），此时用11，12，13的

5、骨牌铺满方格，共有四种铺法。 输入： n（0=n0f(0)=a n=0则称函数f为递归函数（递归公式），为了求f(n)，我们必须先求f(n-1)，为了求f(n-1),又必须去求f(n-2)，为了求f(1),必须先求f(0),而f(0)是已知的。这种定义函数的方式称为递归定义。递 归一个递归定义必须是有确切含义的，也就是说一步比一步简单，最终是有终结的，决不能无限循环下去。比如上例中的f(0)=a，这种最简单的情况（终结条件），称为递归边界，它是递归定义必不可少的一部分。 描述递归定义的函数或求解递归问题的过程称为递归算法。递 归不论是递归过程，还是递归函数，按其调用的方式一般分为直接递归（子程

6、序P直接调用自己）和间接递归（子程序P调用其它子程序，其它子程序又调用P）。 递 归递归算法一般适用在三个场合：一是数据的定义形式是递归的，如求Fibonacci数列问题；二是数据之间的逻辑关系（即数据结构）是递归的，如树、图等的定义和操作；三是某些问题虽然没有明显的递归关系或结构，但问题的解法是不断重复执行一种操作，只是问题规模由大化小，直至某个原操作（基本操作）就结束，如汉诺塔问题，这种问题使用递归思想来求解比其它方法更简单。 递 归递归不仅可用于计算、计数，而且还可用于枚举，即把所有具有各某种特性的对象完全枚举出来，关键是如何从输入参数与输出结果之间的对应关系中归纳出递归公式和边界条件。

7、 递归的应用举例 【例题4】集合的划分【问题描述】设是一个具有n个元素的集合，a1，a2，an，现将划分成K个满足下列条件的子集合s1，s2，sk ，且满足：1si2sisj (1i，jk ij)3s1s2s3sk则称s1，s2，sk是集合的一个划分。它相当于把集合中的n个元素a1 ，a2，an 放入k个（0knk，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)的递归关系式为：s(n，k)s(n1，k1)+k*s(n1，k) (nk，k0)s(n，k)0 (n=2，则 hanoi(n-1，A，C，B) AC hanoi(n-1，B，A，C) 运行结果：Enter the number of disks in Hanoi tower：3ACABCBACBABCAC语句： Hanoi(3，A，B，C)在执行过程中，递归工作栈要为每一层的递归保留数据，由于递归过程hanoi只含有四个值参数，也无其它局部变量，因