递归算法适用的一般场合为：
① 数据的定义形式按递归定义。 如裴波那契数列的定义：
1n 0
fn
2n 1
f n1 f n2 n 2
对应的递归程序为
function fib(n: Integer): Integer;
begin
if n = 0 then
fib := 1
{递归边界}
else if n = 1 then
用过程式move(n-1,a,b,c); 3. 将a柱上剩下的一片直接移到C柱上； 4. 用a柱作为协助过渡，将b柱上的(n-1)片移到c柱上，调
用过程move(n-1,b,c,a)；
源程序见附件
新汉诺（hanoi）塔问题
设有n各大小不等的中空圆盘，按从小到大的顺序从1到n编号。将这n个圆盘 任意的迭套在三根立柱上，立柱的编号分别为A、B、C，这个状态称之为初始 状态。问题要求找到一种步数最少的移动方案，使得从初始状态转变为目标 状态。移动时有如下要求：
递归有如下特点：
①它直接或间接的调用了自己。
②一定要有递归终止的条件，这个条件通常称为边界条件。
与递推一样，每一个递推都有其边界条件。但不同的是，递推是由边界条 件出发，通过递推式求f(n)的值，从边界到求解的全过程十分清楚；而递 归则是从函数自身出发来达到边界条件，在通过边界条件的递归调用过程 中，系统用堆栈把每次调用的中间结果（局部变量和返回地址）保存起来， 直至求出递归边界值f(0)=a。然后返回调用函数。返回的过程中，中间结 果 相 继 出 栈 恢 复 ， f(1)=g(1,a)f(2)=g(2,f(1))…… 直 至 求 出 f(n)=g(n,f(n-1))。
fib := 2
{递归边界}
else
fib := fib(n – 2) + fib(n – 1);
{递归}
end;
② 数据之间的关系（即数据结构）按递归定义。如树 的遍历，图的搜索等。
③ 问题解法按递归算法实现。例如回溯法等。
对于②和③，可以用堆栈结构将其转换为非递归算法， 以提高算法的效率以及减少内存空间的浪费。
递归实例1
例如，我们可以这样定义N!，N!=N*(N-1)!，因此求N!转 化为求 (N-1)!。这就是一个递归的描述。
因此，可以编写如下递归程序： program Factorial; var
n!
n 1
*
(n
1)!
N: Integer;
T: Longint;
function Fac(N: Integer): Longint;
A
B
C
N=3初始状态 1From a to c
2From a to b
3From c to b
4From a to c
5From b to a 6From b to c 7From a to c
假设把第3步、第4步、第7步抽出来就相当于 n=2的情况（把上面2片捆在一起视为一片）
A
B
C
原问题：欲将a柱上的n片移到c柱 上，b柱为过渡柱，记为（a,c,b）
begin
if N = 0 then Fac := 1 else Fac := N * Fac(N - 1)
end;
begin
Write('N = '); Readln(N);
T := Fac(N);
Writeln('N! = ',T);
end.
n0 n0
下图展示了N=3的执行过程。由上述程序可以看出，递归 是一个反复执行直到递归终止的过程。
1、将a柱上的(n-1)片移到b柱上； {a为源柱，b为目标柱，c为过渡 柱}，记为（a,b,c）;
2、将a柱上剩下的1片直接移到c 柱上；{不需要调用过程}；
3、将b柱上的(n-1)片移到c柱上； {b为源柱，c为目标柱，a为过渡 柱}，记为（b,c,a）;
这样就可以把n的状态转换为n-1的状态： 1. 如果n=0，则退出结束程序，否则继续往下执行； 2. 用C柱作为协助过渡，将பைடு நூலகம்柱上的n-1片移到b柱上，调
递归算法
胡苗坤
什么是递归
什么是递归？先看大家都熟悉的一个民间故事：从前有座山，山上 有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说，从前有座山，山 上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说……。象这样， 一个对象部分地由它自己组成，或者是按它自己定义，我们称之是递归。递 归算法作为计算机程序设计中的一种重要的算法，是较难理解的算法之一。 简单地说，递归就是编写这样的一个特殊的过程，该过程体中有一个语句用 于调用过程自身（称为递归调用）。递归过程由于实现了自我的嵌套执行， 使这种过程的执行变得复杂起来，其执行的流程可以用图所示。
汉诺塔问题
有n个圆盘，依半径大小（半径都不同）自下而上套 在a柱上，每次只允许移动最上面一个圆盘到另外的 柱子上去（除a柱外，还有b柱和c柱，开始时这两个柱 子上无圆盘），但绝不允许发生柱子上出现大盘子在 上，小盘子在下的情况，现要求设计将a柱上的n个圆 盘搬移到c柱的方法。
分析：这个移动过程很复杂与烦琐，但规律性却很强。使用递归调用技术来解决这
我们看到，步骤2只需移动一次就可以完成；步骤1与3的操作则完全相同， 唯一区别 仅在于各杆的作用有所不同。这样，原问题被转换为与原问题相同性质的、规模小 一些的新问题（如图）。即：
HANOI(N,A,B,C) 可转化为 HANOI(N-1,A,C,B)与 HANOI(N-1,B,A,B) 其中HANOI中的参数分别表示需移动的盘数、起始盘、临时盘与终止盘， 这种转换 直至转入的盘数为0为止，因为这时已无盘可移了。 这就是需要找的递归调用模型。
个移动过程，先得找到一个递归调用模型。想要得到汉诺塔问题的简单解法，着眼 点应该是移动A杆最底部的大盘，而不是其顶部的小盘。不考虑64个盘而考虑N个盘 的一般情况。要想将A杆上的N个盘移至C杆，我们可以这样设想：
1.以C盘为临时杆，从A杆将1至N-1号盘移至B杆。 2.将A杆中剩下的第N号盘移至C杆。 3.以A杆为临时杆，从B杆将1至N-1号盘移至C杆。
递归按其调用方式分
直接递归——递归过程P直接自己调用自己；
间接递归——即P包含另一过程D，而D又调用P；
由此可见，递归算法的效率往往很低，费时和费内存空间。但是递归也有 其长处，它能使一个蕴含递归关系且结构复杂的程序简洁精炼，增加可读 性。特别是在难于找到从边界到解的全过程的情况下，如果把问题进一步， 其结果仍维持原问题的关系，则采用递归算法编程比较合适。