信息学奥赛之递归优秀课件

1、.1递 归.2递归的定义递归的定义 所谓递归就是一个函数或过程可以直接或间接所谓递归就是一个函数或过程可以直接或间接地调用自己。地调用自己。我们大家都熟悉一个民间故事：从前有一座山，山上有一座庙，庙里有一个老和尚正在给小和尚讲故事，故事里说，从前有一座山，山上有一座庙，庙里有一个老和尚正在给小和尚讲故事，故事里的故事是说。象这种形式，我们就可以称之为递归的一种形象描述，老和尚什么时候不向下讲了，故事才会往回返，最终才会结束。再如：前面多次提到的求再如：前面多次提到的求N!的问题。的问题。我们知道：当我们知道：当N0时，时，N!=N*(N-1)!，因此，求，因此，求N!的问题化成的问题化成了求了

2、求N*(N-1)!的问题，而求的问题，而求(N-1)!的问题又与求的问题又与求N!的解法相同，的解法相同，只不过是求阶乘的对象的值减去了只不过是求阶乘的对象的值减去了1，当，当N的值递减到的值递减到0时，时，N!=1，从而结束以上过程，求得了，从而结束以上过程，求得了N!的解。的解。.3也就是说，求解也就是说，求解N!的过程可以用以下递归方法来表示：的过程可以用以下递归方法来表示： 在这里，为了定义n!，就必须先定义(n-1)!，为了定义(n-1)!，又必须先定义(n-2)!，上述这种用自身的简单情况来定义自己的方式称为递归定义。递归定义。一个递归定义必须是有确切含义的，也就是说，必须一步比一

3、步简单，最后是有终结的，决不允许无限循环下去。上面的例子中，当N=0时定义一个数1，是最简单的情况，称为递归的边界，它本身不再使用递归定义。每一递归都有其边界条件。每一递归都有其边界条件。递归是从自身出发来达到边界条件。 .4递归的调用递归的调用 在在Pascal程序中，子程序可以直接自己调用自己或间程序中，子程序可以直接自己调用自己或间接调用自己，则将这种调用形式称之为递归调用。接调用自己，则将这种调用形式称之为递归调用。递归调用时必须符合以下三个条件：递归调用时必须符合以下三个条件： （1）可将一个问题转化为一个新的问题，而新问题的）可将一个问题转化为一个新的问题，而新问题的解决方法仍与原

4、问题的解法相同，只不过所处理的对象有所解决方法仍与原问题的解法相同，只不过所处理的对象有所不同而已，即它们只是有规律的递增或递减。不同而已，即它们只是有规律的递增或递减。 （2）可以通过转化过程使问题回到对原问题的求解。）可以通过转化过程使问题回到对原问题的求解。 （3）必须要有一个明确的结束递归的条件，否则递归）必须要有一个明确的结束递归的条件，否则递归会无止境地进行下去。会无止境地进行下去。 下面我们通过一些例子，来解释递归程序的设计。下面我们通过一些例子，来解释递归程序的设计。 .5program aa; var t:longint; n:integer; function fac(n:

5、integer):longint; begin if n=0 then fac:=1 else fac:=fac(n-1)*n; end;例例1：按照以上的分析，用递归的方法来求：按照以上的分析，用递归的方法来求N！的解。！的解。程序如下：程序如下：测试数据：测试数据：输入：输入：input n=5输出：输出：5! =120begin write(input n=); read(n); if n0 then writeln(n0,data errer) else begin t:=fac(n); writeln(n,! =,t) end end.6如图展示了程序的执行过程：如图展示了程序的执行

6、过程：.7例例2：读入一串字符倒序输出，以字符：读入一串字符倒序输出，以字符&为结束标志，用过为结束标志，用过程来实现。程来实现。分析：由题意可知，读一串字符当然只能一个个地读入，要分析：由题意可知，读一串字符当然只能一个个地读入，要倒序输出，就要一直读到字符倒序输出，就要一直读到字符&。如输入的一段字符为。如输入的一段字符为ABCDEFGH&，则倒序输出的结果应该是，则倒序输出的结果应该是&HGFEDCBA。 （1）读入一个字符；）读入一个字符；（2）读（该字符后的）子串并倒序输出；）读（该字符后的）子串并倒序输出；（3）然后输出读入字符（指（）然后输出读入字

7、符（指（1）读入的字符）读入的字符）（4）在（）在（2）中若子串是空（即遇字符）中若子串是空（即遇字符&），表示子串），表示子串已完，不再处理子串。已完，不再处理子串。 以上（以上（2）表示一操作依赖另一操作，所以需要用递归调）表示一操作依赖另一操作，所以需要用递归调用。（用。（4）表示已知操作（递归的终止）。）表示已知操作（递归的终止）。.8程序如下：程序如下：program aa; procedure reverse; var ch:char; begin read(ch); if ch& then reverse; write(ch); end; begin revers

8、e; writeln; end.测试数据：测试数据：输入：输入：abcdefghijklmn&输出：输出：&nmlkjihgfedcba.9例例3：利用递归，将一个十进制整数：利用递归，将一个十进制整数K转化为转化为N进制整数（进制整数（N=10）。）。 测试数据：测试数据：输入：输入：K和和N的值的值19 3输出：转化后的输出：转化后的N进制整数进制整数201program aa; var n,k:integer; procedure tentok(k,n:integer); var r:integer; begin r:=k mod n; k:=k div n; if k0

9、 then tentok(k,n); write(r); end;begin read(k,n); tentok(k,n); writeln; end.10递归的一般适合场合1数据的定义形式是按递归定义的数据的定义形式是按递归定义的.如：裴波那契数列的定义为：如：裴波那契数列的定义为：Fn=Fn-1+Fn-2 F1=0 F2=1begin read(n); s:=fib(n); writeln(s); end.测试数据：测试数据：输入：输入：5输出：输出：3program aa; var n:integer; s:longint; Function FIB(N:integer):integer

10、; Begin If n=1 then FIB:=0 Else if n=2 then FIB:=1 Else FIB:=FIB(n-1)+FIB(n-2) End;.112某些问题虽然没有明显的递归关系或结构，但问题的解法是不断重复执行一种操作，只是问题规模由大化小，直至某个原操作（基本操作）就结束，如汉诺塔问题，这种问题使用递归思想来求解比其它方法更简单。 .51.判断运行结果1.program d1; var s,n:integer; function f(n:integer):integer; begin if n=1 then f:=1 else f:=n*n+f

11、(n-1); end; begin write(input n:);readln(n); s:=f(n); writeln(f(,n,)=,s) end.输入输入:input n:3输出输出:练习.16program d2; var a,b:integer; function f(n:integer):integer; begin if n=1 then f:=1 else if n=2 then f:=2 else f:=f(n-1)+f(n-2); end; begin read(a); b:=f(a); writeln(b); end.输入输入:4输出输出:2判断运行结果.17progr

12、am d3; var a,b,c,d:integer; procedure p(a:integer; var b:integer); var c:integer; begin a:=a+1;b:=b+1;c:=2;d:=d+1; writeln(m,a,b,c,d); if a=3时时f(N)=f(N-1)+f(N-2).20请计算请计算ack(m,n)的值。的值。(m,n=n）的最大公约数，应先将）的最大公约数，应先将m除以除以n；求得；求得余数余数r,如果等于零，除数如果等于零，除数n就是就是m,n的最大公约数；的最大公约数；如果如果r不等于零，就用不等于零，就用n除以除以r，再看所得余数是否，再看所得余数是否为零。重复上面过程，直到余数为零。重复上面过程，直到余数r为零时，则上一为零时，则上一次的余数值即为次的余数值即为m,n的最大公约数。用其数学方的最大公约数。用其数学方式描述如下式描述如下:.23program aa; var m,n,t:integer; function f(m,n:integer):integer; var r:integer; begin if (m mod n)=0 then f:=n else begin r:=m mod n; f:=f(n,r); end; end;begin readln(m,n); if