递归与回溯算法教学内容.ppt

《递归与回溯算法教学内容.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、递归与回溯算法递归的调用在Pascal程序中，子程序可以直接自己调用自己或间接调用自己，则将这种调用形式称之为递归调用。其中，我们将前者的调用方式称为简单递归，后者称为间接递归。由于目前我们介绍、掌握的知识尚还无法实现间接递归，只有留待在以后的内容中我们再作介绍。本节只介绍直接递归。递归调用时必须符合以下三个条件：（1）可将一个问题转化为一个新的问题，而新问题的解决方法仍与原问题的解法相同，只不过所处理的对象有所不同而已，即它们只是有规律的递增或递减。（2）可以通过转化过程使问题回到对原问题的求解。（3）必须要有一个明确的结束递归的条件，否则递归会无止境地进行下去。下面

2、我们通过一些例子，来解释递归程序的设计。2programaa;vart:longint;n:integer;functionfac(n:integer):longint;beginifn=0thenfac:=1elsefac:=fac(n-1)*n;end;例1：按照以上的分析，用递归的方法来求N！的解。程序如下：测试数据：输入：inputn=5输出：5!=120beginwrite('inputn=');read(n);ifn<0thenwriteln('n<0,dataerrer')elsebegint:=fac(n);writeln(n,'!=',t)endend

3、.3如图展示了程序的执行过程：在这里，因为函数FAC的形参是值形参，因此每调用一次该函数，系统就为本次调用的值形参N开辟了一个存储单元，以便存放它的实参的值。也就是说，对于递归函数或递归过程，每当对它调用一次时，系统都要为它的形式参数与局部变量（在函数或过程中说明的变量）分配存储单元（这是一个独立的单元，虽然名字相同，但实际上是互不相干的，只在本层内有效），并记下返回的地点，以便返回后程序从此处开始执行。4例2：读入一串字符倒序输出，以字符’&’为结束标志，用过程来实现。分析：由题意可知，读一串字符当然只能一个个地读入，要倒序输出，就要一直读到字符’&’。如输入的一段字

4、符为ABCDEFGH&’，则倒序输出的结果应该是’&HGFEDCBA’。（1）读入一个字符；（2）读（该字符后的）子串并倒序输出；（3）然后输出读入字符（指（1）读入的字符）（4）在（2）中若子串是空（即遇字符’&’），表示子串已完，不再处理子串。以上（2）表示一操作依赖另一操作，所以需要用递归调用。（4）表示已知操作（递归的终止）。5程序如下：programaa;procedurereverse;varch:char;beginread(ch);ifch<>'&'thenreverse;write(ch);end;beginreverse;writeln;end.测试

5、数据：输入：abcdefghijklmn&输出：&nmlkjihgfedcba6例3：利用递归，将一个十进制整数K转化为N进制整数（N<=10）。测试数据：输入：K和N的值193输出：转化后的N进制整数201programaa;varn,k:integer;proceduretentok(k,n:integer);varr:integer;beginr:=kmodn;k:=kdivn;ifk<>0thententok(k,n);write(r);end;beginread(k,n);tentok(k,n);writeln;end.7递归的一般适合场合1．数据的定义形式是

6、按递归定义的.如：裴波那契数列的定义为：Fn=Fn-1+Fn-2F1=0F2=1beginread(n);s:=fib(n);writeln(s);end.测试数据：输入：5输出：3programaa;varn:integer;s:longint;FunctionFIB(N:integer):integer;BeginIfn=1thenFIB:=0Elseifn=2thenFIB:=1ElseFIB:=FIB(n-1)+FIB(n-2)End;8例如；著名的Hanoi塔（汉诺塔）问题。3．数据之间的结构关系按递归定义的例如：大家将在后面的学习内容中遇到的树的遍历、图的搜

7、索等问题。2．问题的求解方法是按递归算法来实现的。9判断运行结果1.programd1;vars,n:integer;functionf(n:integer):integer;beginifn=1thenf:=1elsef:=n*n+f(n-1);end;beginwrite('inputn:');readln(n);s:=f(n);writeln('f(',n,')=',s)end.输入:inputn:3输出:练习一102．programd2;vara,b:integer;functionf(n:integer):integer;beg