（2） 过程的描述中包含它本身；
在设计递归算法中，如何将一个问题转化为递归的问题，是初学者面临的难题，下面我们通过分析汉诺塔问题，看看如何用递归算法来求解问题；
递归算法应用
例1：汉诺塔问题，如下图，有A、B、C三根柱子。A柱子上按从小到大的顺序堆放了N个盘子，现在要把全部盘子从A柱移动到C柱，移动过程中可以借助B柱。移动时有如下要求：
（1） 一次只能移动一个盘子；
（2） 不允许把大盘放在小盘上边； （3） 盘子只能放在三根柱子上；
算法分析：当盘子比较多的时，问题比较复杂，所以我们先分析简单的情况： 如果只有一个盘子，只需一步，直接把它从A柱移动到C柱； 如果是二个盘子，共需要移动3步: （1） 把A柱上的小盘子移动到B柱; （2） 把A柱上的大盘子移动到C柱； （3） 把B柱上的大盘子移动到C柱；
如果N比较大时，需要很多步才能完成，我们先考虑是否能把复杂的移动过程转化为简单的移动过程，如果要把A柱上最大的盘子移动到C柱上去，必须先把上面的N-1个盘子从A柱移动到B柱上暂存，按这种思路，就可以把N个盘子的移动过程分作3大步：
（1） 把A柱上面的N-1个盘子移动到B柱； （2） 把A柱上剩下的一个盘子移动到C柱； （3） 把B柱上面的N-1个盘子移动到C柱；
其中N-1个盘子的移动过程又可按同样的方法分为三大步，这样就把移动过程转化为一个递归的过程，直到最后只剩下一个盘子，按照移动一个盘子的方法移动，递归结束。
递归过程：
procedure Hanoi(N,A,B,C:integer;)；{以B柱为中转柱将N个盘子从A柱移动到C柱} begin
if N=1 then write(A,’->’,C){把盘子直接从A移动到C} else begin
Hanoi(N-1,A,C,B)；{ 以C柱为中转柱将N-1个盘子从A柱移动到B柱} write(A,’->’,C)；{把剩下的一个盘子从A移动到C}
Hanoi(N-1,B,A,C)； { 以A柱为中转柱将N-1个盘子从B柱移动到C柱} end; end;
从上面的例子我们可以看出，在使用递归算法时，首先弄清楚简单情况下的解法，然后弄清楚如何把复杂情况归纳为更简单的情况。
在信息学奥赛中有的问题的结构或所处理的数据本身是递归定义的，这样的问题非常适合用递归算法来求解，对于这类问题，我们把它分解为具有相同性质的若干个子问题，如果子问题解决了，原问题也就解决了。
例2求先序排列 (NOIP2001pj)
[问题描述]给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示，长度≤8)。 [样例] 输入：BADC BDCA 输出：ABCD
算法分析：我们先看看三种遍历的定义：
先序遍历是先访问根结点，再遍历左子树，最后遍历右子树； 中序遍历是先遍历左子树，再访问根结点，最后遍历右子树； 后序遍历是先遍历左子树，再遍历右子树，最后访问根结点；
从遍历的定义可知，后序排列的最后一个字符即为这棵树的根节点；在中序排列中，根结点前面的为其左子树，根结点后面的为其右子树；我们可以由后序排列求得根结点，再由根结点在中序排列的位置确定左子树和右子树，把左子树和右子树各看作一个单独的树。这样，就把一棵树分解为具有相同性质的二棵子树，一直递归下去，当分解的子树为空时，递归结束，在递归过程中，按先序遍历的规则输出求得的各个根结点，输出的结果即为原问题的解。 源程序
program noip2001_3; var z,h : string;
procedure make(z,h:string); {z为中序排列,h为后序排列} var s,m : integer; begin
m:=length(h);{m为树的长度} write(h[m]); {输出根节点}
s:=pos(h[m],z); {求根节点在中序排列中的位置}
if s>1 then make(copy(z,1,s-1),copy(h,1,s-1)); {处理左子树} if m>s then make(copy(z,s+1,m-s),copy(h,s,m-s)); {处理右子树} end; begin
readln(z); readln(h); make(z,h); end.
递归算法不仅仅是用于求解递归描述的问题，在其它很多问题中也可以用到递归思想，如回溯法、分治法、动态规划法等算法中都可以使用递归思想来实现，从而使编写的程序更加简洁。
比如上期回溯法所讲的例2《数的划分问题》，若用递归来求解，程序非常短小且效率很高，源程序如下
var
n,k:integer; tol:longint;
procedure make(sum,t,d:integer); var i:integer; begin
if d=k then inc(tol)
else for i:=t to sum div 2 do make(sum-i,i,d+1); end; begin
readln(n,k); tol:=0;
make(n,1,1); writeln(tol); end.
有些问题本身是递归定义的，但它并不适合用递归算法来求解，如斐波那契(Fibonacci)数列，它的递归定义为：
F(n)=1 (n=1,2)
F(n)=F(n-2)+F(n-1) (n>2) 用递归过程描述为：
Funtion fb(n:integer):integer; Begin
if n<3 then fb:=1
else fb:=fb(n-1)+fb(n-2); End;
上面的递归过程，调用一次产生二个新的调用，递归次数呈指数增长，时间复杂度为O（2n）,把它改为非递归： x:=1;y:=1;
for i:=3 to n do begin
z:=y;y:=x+y;x:=z; end;
修改后的程序，它的时间复杂度为O（n）。
我们在编写程序时是否使用递归算法，关键是看问题是否适合用递归算法来求解。由于递归算法编写的程序逻辑性强，结构清晰，正确性易于证明，程序调试也十分方便，在NOIP中，数据的规模一般也不大，只要问题适合用递归算法求解，我们还是可以大胆地使用递归算法。
算法在信息学奥赛中的应用 (递推法)
所谓递推，是指从已知的初始条件出发，依据某种递推关系，逐次推出所要求的各中间结果及最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简后确定。
可用递推算法求解的题目一般有以下二个特点： （1） 问题可以划分成多个状态；
（2） 除初始状态外，其它各个状态都可以用固定的递推关系式来表示。 在我们实际解题中，题目不会直接给出递推关系式，而是需要通过分析各种状态，找出递推关系式。
递推法应用
例1骑士游历:（noip1997tg）
设有一个n*m的棋盘(2<=n<=50,2<=m<=50),如下图,在棋盘上任一点有一个中国象棋马,
马走的规则为:1.马走日字 2.马只能向右走，即如下图所示:
任务1:当N,M 输入之后,找出一条从左下角到右上角的路径。 例如:输入 N=4,M=4
输出:路径的格式:(1,1)->(2,3)->(4,4) 若不存在路径,则输出\
任务2:当N,M 给出之后,同时给出马起始的位置和终点的位置,试找出从起点到终点的所有路径的数目。
例如:(N=10,M=10),(1,5)(起点),(3,5)(终点)
输出:2(即由(1,5)到(3,5)共有2条路径)
输入格式:n,m,x1,y1,x2,y2(分别表示n,m,起点坐标,终点坐标) 输出格式:路径数目(若不存在从起点到终点的路径,输出0)
算法分析：为了研究的方便，我们先将棋盘的横坐标规定为i，纵坐标规定为j，对于一个n×m的棋盘，i的值从1到n，j的值从1到m。棋盘上的任意点都可以用坐标(i,j)表示。对于马的移动方法，我们用K来表示四种移动方向(1,2,3,4)；而每种移动方法用偏移值来表示，并将这些偏移值分别保存在数组dx和dy中，如下表 K Dx[k] Dy[k] 1 2 3 4 2 2 1 1 1 -1 2 -2 根据马走的规则，马可以由（i-dx[k],j-dy[k]）走到(i,j)。只要马能从（1，1）走到（i-dx[k],j-dy[k]），就一定能走到（i,j）,马走的坐标必须保证在棋盘上。我们以（n,m）为起点向左递推，当递推到（i-dx[k],j-dy[k]）的位置是（1，1）时，就找到了一条从（1，1）到（n,m）的路径。
我们用一个二维数组a表示棋盘，对于任务一，使用倒推法，从终点(n,m)往左递推， 设初始值a[n,m]为（-1，-1），如果从(i,j)一步能走到(n,m)，就将(n,m)存放在a[i,j]中。如下表，a[3,2]和a[2,3]的值是（4，4），表示从这两个点都可以到达坐标（4,4）。从（1,1）可到达（2，3）、（3，2）两个点，所以a[1,1]存放两个点中的任意一个即可。递推结束以后，如果a[1,1]值为(0,0)说明不存在路径，否则a[1,1]值就是马走下一步的坐标，以此递推输出路径。 -1,-1 4,4 4,4 2,3 任务一的源程序：
const
dx:array[1..4]of integer=(2,2,1,1);
信息学奥赛——算法入门教程
