第二章递归技术.pptVIP

二、特征方程及特征根法 * 第2章 递归技术第一节 递归技术 一个直接或间接地调用自身的过程叫做递归过程（recursive procedure）。一个使用函数自身给出定义的函数叫做递归函数（recursive function）。在计算机算法中，递归技术是颇有用处的，其应用往往使函数的定义和算法的描述比使用非递归方法更好。有些数据结构如二叉树等，由于其本身固有的递归特性，特别适合用递归的形式来描述。 * 1.1 引言 一、阶乘 阶乘函数的递归定义如下： 第二式是用较小自变量的函数值来表达较大自变量的函数值。定义的左右两边都引用了阶乘记号，是一个递归定义式。上述定义用程序设中的记号表示为： FAC（0）=1 FAC（n）=FAC（n-1）*n（n0） 也可以采用非递归方式定义 * 可递归地计算如下： int factorial(int n) { if (n==0) return 1; return n* factorial(n-1); } * 二、斐波那契级数 斐波那契（Fibonacci leonardo，约1170-1250）是意大利著名数学家。他最重要的研究成果是在不定分析和数论方面。他是在研究兔子的生长、繁殖的规律中发现这一数列的。他对数列的研究是从一对刚刚出生的小兔子（雌雄一对）开始计算在n个月后将会有多少只兔子，他做了如下的假设： 1、新出生的小兔子在一个月的时间里发育为成年兔子，第3个月开始可以繁殖一对小兔子； 2、每对成年兔子每月繁殖一对小兔子（雌雄一对）； 3、兔子没有死亡发生。问一年中，每个月各有多少对兔子？ 用Fn代表n个月后兔子的对数。因为从一对新生的兔子开始，所以，F0=1，F1=1。这一对兔子在第二个月末生出另一对小兔子，从而F2=1+1=2。在第三个月末，第一对兔子将生下又一对小兔子，所以F3=2+1=3。我们用如下的表格表示前10个月每个月初兔子的数量： 时间(月) 初生兔子(对) 成熟兔子(对) 兔子总数(对) 1 1 0 1 2 0 1 1 3 1 1 2 4 1 2 3 5 2 3 5 6 3 5 8 7 5 8 13 8 8 13 21 9 13 21 34 10 21 34 55 由此可知，从第一个月开始以后每个月的兔子总数是: 1,1,2,3,5,8,13,21,34,55,89,144,233… * 二、斐波那契级数 无穷数列0，1，2，3，5，8，13，21，34，55……，称为Fibonacci级数，可以用下面递归关系式定义 F（0）=0 F（1）=1 F（n）=F（n-1）+F（n-2）（n≥2） 第三式是一个递归关系式，当n大于等于2时，这个级数的第n项的值是前面的项之和。它用两个较小的自变量的函数值来定义一个较大自变量的函数值，需两个初始值F（0）和F（1），计算F（n），要递归调用F（n-1）和F（n-2），即递归两次，而为了计算F（n-1）要利用已调用的F（n-2）外，还要调用F（n-3），如此等等。为计算F（n）必作n次递归调用，调要次数称为递归深度，它可用来量度一个递归函数的计算复杂性。 * 1.1 引言 第n个Fibonacci数可递归地计算如下： int fibonacci(int n) { if (n=1) return 1; return fibonacci(n-1)+ fibonacci(n-2); } * 三、阿克曼（Ackerman）函数 阿克曼函数是一个双递归函数，就是指函数及它的一个自变量均由它本身来定义的函数。 * * 四、整数分划（partition） * * * 计算Q（n，m）的递归函数如下： int Q(int n, int m) { if ((n1)||m1)) return 0; if ((n==1)||(m==1)) return 1; if (nm) return Q(n,n); if (n==m) return Q(n,m-1)+1; return Q(n,m-1)+Q(n-m,m); } * 五、递归算法的实现 递归算法执行时，需要多次调用自身，实现这种递归调用的关键是为算法建立递归调用工作栈。一个算法调用另一个算法之前需要执行下面3步工作： 将所有实参指针、返回地址等信息传递给被调用的算法； 为被调用算法的局部变量分配存储区； 将控制转移到被调用算法的入口。