文档介绍：递归与回溯算法
*
第一页，课件共52页
递归的定义
所谓递归就是一个函数或过程可以直接或间接地调用自己。我们大家都熟悉一个民间故事：从前有一座山，山上有一座庙，庙里有一个老和尚正在给小和尚讲故事，故事里说，从前有一座山，山上有一座庙，庙里有一个老和尚正在给小和尚讲故事，故事里的故事是说……。象这种形式，我们就可以称之为递归的一种形象描述，老和尚什么时候不向下讲了，故事才会往回返，最终才会结束。
再如：前面多次提到的求N!的问题。
我们知道：当N>0时，N!=N*(N-1)!，因此，求N!的问题化成了求N*(N-1)!的问题，而求(N-1)!的问题又与求N!的解法相同，只不过是求阶乘的对象的值减去了1，当N的值递减到0时，N!=1，从而结束以上过程，求得了N!的解。
*
第二页，课件共52页
也就是说，求解N!的过程可以用以下递归方法来表示：
在这里，为了定义n!，就必须先定义(n-1)!，为了定义(n-1)!，又必须先定义(n-2)!……，上述这种用自身的简单情况来定义自己的方式称为递归定义。
一个递归定义必须是有确切含义的，也就是说，必须一步比一步简单，最后是有终结的，决不允许无限循环下去。
上面的例子中，当N=0时定义一个数1，是最简单的情况，称为递归的边界，它本身不再使用递归定义。
与递推一样，每一递归都有其边界条件。但不同的是，递推是由边界条件出发，通过递推式来求值，而递归则是从自身出发来达到边界条件。
*
第三页，课件共52页
递归的调用
在Pascal程序中，子程序可以直接自己调用自己或间接调用自己，则将这种调用形式称之为递归调用。
其中，我们将前者的调用方式称为简单递归，后者称为间接递归。由于目前我们介绍、掌握的知识尚还无法实现间接递归，只有留待在以后的内容中我们再作介绍。本节只介绍直接递归。
递归调用时必须符合以下三个条件：
（1）可将一个问题转化为一个新的问题，而新问题的解决方法仍与原问题的解法相同，只不过所处理的对象有所不同而已，即它们只是有规律的递增或递减。
（2）可以通过转化过程使问题回到对原问题的求解。
（3）必须要有一个明确的结束递归的条件，否则递归会无止境地进行下去。
下面我们通过一些例子，来解释递归程序的设计。
*
第四页，课件共52页
program aa;
var
t:longint;
n:integer;
function fac(n:integer):longint;
begin
if n=0 then fac:=1
else fac:=fac(n-1)*n;
end;
例1：按照以上的分析，用递归的方法来求N！的解。
程序如下：
测试数据：
输入：
input n=5
输出：
5! =120
begin
write('input n=');
read(n);
if n<0 then writeln('n<0,data errer')
else
begin
t:=fac(n);
writeln(n,'! =',t)
end
end.
*
第五页，课件共52页
如图展示了程序的执行过程：
在这里，因为函数FAC的形参是值形参，因此每调用一次该函数，系统就为本次调用的值形参N开辟了一个存储单元，以便存放它的实参的值。也就是说，对于递归函数或递归过程，每当对它调用一次时，系统都要为它的形式参数与局部变量（在函数或过程中说明的变量）分配存储单元（这是一个独立的单元，虽然名字相同，但实际上是互不相干的，只在本层内有效），并记下返回的地点，以便返回后程序从此处开始执行。
*
第六页，课件共52页
例2：读入一串字符倒序输出，以字符’&’为结束标志，用过程来实现。
分析：由题意可知，读一串字符当然只能一个个地读入，要倒序输出，就要一直读到字符’&’。如输入的一段字符为ABCDEFGH&’，则倒序输出的结果应该是’&HGFEDCBA’。
（1）读入一个字符；
（2）读（该字符后的）子串并倒序输出；
（3）然后输出读入字符（指（1）读入的字符）
（4）在（2）中若子串是空（即遇字符’&’），表示子串已完，不再处理子串。
以上（2）表示一操作依赖另一操作，所以需要用递归调用。（4）表示已知操作（递归的终止）。
*
第七页，课件共52页
程序如下：
program aa;
procedure reverse;
var
ch:char;
begin
read(ch);
if ch<>'&' then