[算法分析] 为了描述问题的某一状态，必须用到它的上一状态，而描述上一状态，又必须用到它的上一状态……这
种用自已来定义自己的方法，称为递归定义。例如：定义函数f(n)为：
/n*f(n－1) (n>0)
f(n)= |
\ 1(n=0)
则当0时，须用f(n-1)来定义f(n),用f(n-1-1)来定义f(n-1)……当n=0时，f(n)=1。
由上例我们可看出，递归定义有两个要素：
（1）递归边界条件。也就是所描述问题的最简单情况，它本身不再使用递归的定义。
如上例，当n=0时，f(n)=1，不使用f(n-1)来定义。
（2）递归定义：使问题向边界条件转化的规则。递归定义必须能使问题越来越简单。
如上例：f(n)由f(n-1)定义，越来越靠近f(0),也即边界条件。最简单的情况是f(0)=1。
递归算法的效率往往很低, 费时和费内存空间. 但是递归也有其长处, 它能使一个蕴含递归关系且结构
复杂的程序简介精炼, 增加可读性. 特别是在难于找到从边界到解的全过程的情况下, 如果把问题推进一步
没其结果仍维持原问题的关系, 则采用递归算法编程比较合适.
递归按其调用方式分为: 1. 直接递归, 递归过程P直接自己调用自己; 2. 间接递归, 即P包含另一过程
D, 而D又调用P.
递归算法适用的一般场合为:
1. 数据的定义形式按递归定义.
如裴波那契数列的定义: f(n)=f(n-1)+f(n-2); f(0)=1; f(1)=2.
对应的递归程序为:
Function fib(n : integer) : integer;
Begin
if n = 0 then fib := 1 { 递归边界 }
else if n = 1 then fib := 2
else fib := fib(n-2) + fib(n-1) { 递归 }
End;
这类递归问题可转化为递推算法, 递归边界作为递推的边界条件.
2. 数据之间的关系(即数据结构)按递归定义. 如树的遍历, 图的搜索等.
3. 问题解法按递归算法实现. 例如回溯法等.
从问题的某一种可能出发, 搜索从这种情况出发所能达到的所有可能, 当这一条路走到" 尽头 "
的时候, 再倒回出发点, 从另一个可能出发, 继续搜索. 这种不断" 回溯 "寻找解的方法, 称作
" 回溯法 ".
[参考程序]
下面给出用回溯法求所有路径的算法框架. 注释已经写得非常清楚, 请读者仔细理解.
Const maxdepth = ????;
Type statetype = ??????; { 状态类型定义 }
operatertype = ??????; { 算符类型定义 }
node = Record { 结点类型 }
state : statetype; { 状态域 }
operater :operatertype { 算符域 }
End;
{ 注: 结点的数据类型可以根据试题需要简化 }
Var
stack : Array [1..maxdepth] of node; { 存当前路径 }
total : integer; { 路径数 }
Procedure make(l : integer);
Var i : integer;
Begin
if stack[L-1]是目标结点 then
Begin
total := total+1; { 路径数+1 }
打印当前路径[1..L-1];
Exit
End;
for i := 1 to 解答树次数 do
Begin
生成 stack[l].operater;
stack[l].operater 作用于 stack[l-1].state, 产生新状态 stack[l].state;
if stack[l].state 满足约束条件 then make(k+1);
{ 若不满足约束条件, 则通过for循环换一个算符扩展 }
{ 递归返回该处时, 系统自动恢复调用前的栈指针和算符, 再通过for循环换一个算符扩展 }
{ 注: 若在扩展stack[l].state时曾使用过全局变量, 则应插入若干语句, 恢复全局变量在
stack[l-1].state时的值. }
End;
{ 再无算符可用, 回溯 }
End;
Begin
total := 0; { 路径数初始化为0 }
初始化处理;
make(l);
打印路径数total
End.
[例子] 求N个数的全排列。
［分析］求N个数的全排列，可以看成把N个不同的球放入N个不同的盒子中，每个盒子中只能有一
个球。解法与八皇后问题相似。
［参考过程］
procedure try(I:integer);
var j:integer;
begin
for j:=1 to n do
if a[j]=0 then
begin
x[I]:=j;
a[j]:=1;
if I<n then try(I+1)
else print;
a[j]=0;
end;
end;
[习题] 用递归完成：
1、如下图，打印0－N的所有路径(0=〈N〈=9)：
1―> 3―> 5―> 7―> 9
^ ^ ^ ^ ^
| | | | |
0―> 2―> 4―> 6―> 8
(说明：图中须加上0－>3，2－>5，4－>7，6－>9的连线)
2、快速排序。
3、打印杨辉三角。
最后, 给出一道经典的使用回溯算法解决的问题, 留给读者思考.
题目描述:
对于任意一个m*n的矩阵, 求L形骨牌覆盖后所剩方格数最少的一个方案.
网友评论：（只显示最新10条。评论内容只代表网友观点，与本站立场无关！） 
