信息学奥林匹克高级本第一章递归技术.docVIP

递归算法 在过程和函数的学习中，调用子程序的一般形式是：主程序调用子程序，如图1-1：嵌套关系的子程序是上级调用下级，如图1-2：平级关系的子程序是后定义的调用先定义的，如图1-3。 子程序能否调用自己呢？在PASCAL语言中是可以的，我们称之为递归调用。图1-4是子程序A直接调用自己，这称为直接递归；图1-5是嵌套关系的子程序A和B，内层的B调用外层的A，这是间接递归；图1-6是平级关系的子程序A和B，其中A调用了B，B又调用A，这也是间接递归，这种间接递归用到了“超前引用”的规则。 因直接递归使用最多，帮本章着重讨论直接递归。 上面中是从调用子程序的形式上阐述“递归调用”，而递归调用适合解决哪些问题，这才是我们关心的问题本质，通过下面两小节“递归函数”和“递归过程”的学习，我们可以有所体会。 1．1递归函数 数学中有许多函数可以用函数自己来描述，确切地说是用自身的简单情况来定义自己，就是所谓的递归定义。 如，阶乘可以写成n!=(n-1)!*n，这阶乘用阶乘来定义。 阶乘的递归定义为 n! = (n-1)!*n 当n0时 （递归形式的描述） 1 当n=0时 （递归结束的条件） 有了这两点，问题就适宜用递归调用的方法（即递归算法）来解决。下面三个例子来学习。 例1：求n!. 将上面阶乘的递归定义写成为函数f(n)的形式。 f(n)=f(n-1)*n f(0)=1 源程序： Program exp1_1; Function f(n:integer):longint; Begin If n=0 then f:=1 {递归边界} Else f:=f(n-1)*n; {递归调用} End; Begin {main} Writeln(f(3)) End. 运行结果：6 这里将主程序简化了，直接输出函数f(3)即3！的值。下图示意了递归调用函数的过程： 每一个方框代表一次调用，方框上部列出了每次调用所建立的值参n单元中的值，调用顺序是①、②、③、④，主程序调用函数f，求f(3)；求f(3)的过程中又去调用函数f，求f(2)；求f(2)的过程中又去调用函数f，求f(1)；……最终求f(0)，因为到达递归的边界，调用终止，得f(0)=1，由此开始返回；返回的顺序是⑤、⑥、⑦、⑧，方框下部列出了每次调用结束时送回到原表达式中的函数值。 每调用一次函数，系统就为本次调用的值形参n开辟一个存储单元，这些存储单元虽然同名，但各自独立，互不相干（这如同主程序和子程序出现变量同名的问题），递归到哪一层，那一层的变量n就起作用，返回上一层，就释放掉低层的同名变量。 例1-2 给定n（n=1），用递归的方法求1+2+3+4+5+…+n的值。 本来“求连续自然数的和”是个老生常谈的题目，过去都是用循环累加的方法。而这里指定用递归的方法，因此必须考虑两点： 能否将问题转化为递归形式的描述。 是否有递归结束的边界条件 设：函数s(n)=1+2+3+4+5+…+(n-1)+n 显然递归的两个条件都有了： s(n)=s(n-1)+n s(1)=1 源程序： Program exp1_2; Function s(n:integer):integer; Begin If n=1 then s:=1 else s:=s(n-1)+n; End; Begin Write(‘Input n=’); readln(n); If n0 then writeln(‘n0,data error!’) else writeln(‘s=’,s(n)); End. 取n=3代入程序，仿造上例的分析，细细地体会一下递归的过程。 递归的能力在于用有限的语句来定义对象的无限集合。有些数据直接用递归形式来定义，既简单明了又有概括性。如： 例1-3 斐波那契数列0、1、1、2、3、5、8、13、21、34、35、……从第三项开始，每一项都是紧挨着的前两项的和。其递归定义为： { x0=0 x1=1 xn=xn-1+xn-2 (n=2)} 程序略。 递归技术 主要思想：把阶数较高的某一过程，转化为阶数较低的相同类型的过程，称为递归算法。递归的主要思想包括三个方面： 定义形式是递归定义的。如裴波那契数列的定义：F(n)=F(n-1)+F(n-2) ; F(0)=1; F(1)=2 数据之间的关系（即数据结构）按递归定义。如二叉树，其结构本身就具有递归性质，他们的算法实现可用递归来描述。 问题本身没有明显的递归结构，但用递归求解比用迭代求解更简单，如八皇后问题，HANNOI塔问题等。 例题分析： 例1：背包问题：设有一个背包，可放入重量为S。现有n件物品，重量分别为S1，S2，…， S