《2022年递归应用 .pdf》由会员分享，可在线阅读，更多相关《2022年递归应用 .pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、递归应用直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。一个比较经典的描述是老和尚讲故事，他说从前有座山，山上有座庙，庙里有个老和尚在讲故事，他说从前有座山，山上有座庙，庙里有个老和尚在讲故事，他说从前有座山，。这样没完没了地反复讲故事，直到最后老和尚烦了停下来为止。反复讲故事可以看成是反复调用自身，但如果不能停下来那就没有意义了，所以最终还要能停下来。递归的关键在于找出递归方程式和递归终止条件。即老和尚反复讲故事这样的递归方程式要有，最后老和尚烦了停下来这样的递归的终止条件也要有。阶乘的算法可以定义成函数 n*f(n1) (n0) f(n) f(n)=1 (n=
2、0) 当 n0 时，用 f(n-1)来定义 f(n)，用 f(n-1-1)来定义 f(n-1)，这是对递归形式的描述。当 n=0 时， f(n)=1 ，这是递归结束的条件。函数都可以找到相应的非递归方式定义： n!=1*2*3*(n-1)*n 边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。递归算法一般用于解决三类问题：. 数据的定义形式是按递归定义的。比如阶乘的定义。例 1 又如裴波那契数列的定义：f(n)=f(n-1)+f(n-2); f(0)=1; f(1)=2 对应的递归程序为：var n:integer; function f(n:i
3、nteger):longint; begin case n of 0:f:=1; 递归结束条件 1:f:=2; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 6 页 - - - - - - - - - else f:=f(n-1)+f(n-2) 递归调用 end end; begin readln(n); writeln(f(n); end. 这类递归问题往往又可转化成递推算法，递归边界作为递推的边界条件。例 2 Ackerman函数当一个函数及它的一个变量是由函数自身
4、定义时，称这个函数是双递归函数 。Ackerman函数 A(m ，n)定义如下： n+1当 m=0时AKM ( m , n ) = AKM( m -1 ,1) 当 m 0 ， n=0 时 AKM( m-1, AKM( m,n-1) 当 m 0, n 0时Ackerman函数却无法找到非递归的定义。. 问题解法按递归算法实现。例如回溯等。. 数据的结构形式是按递归定义的。如树的遍历, 图的搜索等。递归解决实际问题的例子很多，如经典的梵塔问题。例 2 梵塔问题：有n 个半径各不相同的圆盘，按半径从大到小，自下而上依次套在A柱上，另外还有B、C两根空柱。要求将A柱上的 n 个圆盘全部搬到C柱上去，每
5、次只能搬动一个盘子，且必须始终保持每根柱子上是小盘在上，大盘在下。在移动盘子的过程当中发现要搬动n 个盘子，必须先将n-1 个盘子从 A柱搬到 B柱去，再将A柱上的最后一个盘子搬到C柱，最后从B柱上将 n-1 个盘子搬到C柱去。搬动n 个盘子和搬动n-1 个盘子时的方法是一样的，当盘子搬到只剩一个时，递归结束。程序如下：var a,b,c,number:integer; procedure move(n,a,b,c:integer); begin if n=1 then writeln(a,-,c) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - -
6、- - - - - 名师精心整理 - - - - - - - 第 2 页，共 6 页 - - - - - - - - - else begin move(n-1,a,c,b); writeln(a,-,c); move(n-1,b,a,c) end; end; begin write(the number of dish:); readln(number); move(number,1,2,3); readln end. 自然数的拆分，数字的拆分等都可以用到递归算法。例 3 要求找出具有下列性质的数的个数( 包含输入的自然数n) ：先输入一个自然数n(n=500), 然后对此自然数按照如下方法
7、进行处理: . 不作任何处理 ; . 在它的左边加上一个自然数, 但该自然数不能超过原数的一半; . 加上数后 , 继续按此规则进行处理, 直到不能再加自然数为止. 样例 : 输入 : 6 满足条件的数为 6 16 26 126 36 136 输出 : 6 这道题只需求出满足条件的数的个数，在n 值不大的情况下用递归求解比较方便，因为它本身题目的条件就是递归定义的。递归的样例程序如下：var n,i:integer; s:real; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3
8、 页，共 6 页 - - - - - - - - - procedure qiu(x:integer); var k:integer; begin if x0 then begin s:=s+1; for k:=1 to x div 2 do qiu(k) end end; begin readln(n); s:=0; qiu(n); writeln(s:2:0) end. 递归算法解题通常显得很简洁， 但递归算法解题的运行效率较低。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。 递归次数过多容易造成栈溢出等。递归小结优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法
9、的正确性，因此它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。解决方法：在递归算法中消除递归调用，使其转化为非递归算法。1. 采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。2. 用递推来实现递归函数。3. 通过 Cooper 变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。后两种方法在时空复杂度上均有较大改善，但其适用范围有限。题 1直线的交点数平面上有 n 条直线，且无三线共点，问这些直线能有多少种不同的交点数。名师资料
10、总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 6 页 - - - - - - - - - 输入： n (n=20) 输出：若干行，列出所有相交方案，其中每一行为一个可能的交点数。 样例：输入： 4 输出： 0 3 4 5 6 （表示 4 条直线的情况下，可能有0， 3，4，5，6 个交点）题 2集合的划分设 s是一个具有 n 个元素的集合， sa1,a2, ,an,现将 s 划分为 k 个满足下列条件的子集合 s1，s2， sk，且满足：（1）si（2）si 交 sj=（3）s
11、1并 s2并 s3并并 sks 则称 s1，s2， sk 是集合 s 的一个划分。请你确定n 个元素 a1,a2, ,an 放入 k 个无标号盒子中去的划分数s（n，k）。输入： nk （0k=n30）输出： s（n，k） 样例 ：输入： 4 3 输出： 6题 3Ackerman 函数定义如下：请写出递归算法。 n+1当 m=0 时AKM ( m , n ) = AKM( m-1 ,1) 当 m 0 ，n=0 时 AKM( m-1, AKM( m,n-1) 当 m 0, n 0时 写出计算Ack(m，n) 的递归算法程序。 写出计算 Ack(m，n) 的非递归算法程序。题 4用递归算法把任一给定的十进制正整数m（m=32000 ）转换成八进制数输出。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - 样例：输入： 765 （即 m 的值）输出： 765（1375）8名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -