若子问题还相当大，则可以反复使用分治法，直至最后所分得的子问题足够小，以至可以直接求解为止。
在利用分治法求解时，所得子问题的类型常常和原问题相同，因而很自然地导致递归求解。
例如:
焚塔问题:
Hanoi（n,x,y,z）可以分成三个子问题：
1）Hanoi（n-1,x,z,y）
2）Move（n,‘X’‘Z’）
3）Hanoi（n-1,y,x,z）
n=1时可以直接求解
二叉树的遍历Traverse（BT）分成三个子问题：
1）Visite（RootNode）
2）Traverse（LBT）
3）Traverse（RBT）
对空树不需要遍历
分治法特别适用于结构上可以分解的结构，如:
二叉树、树、广义表等
广义表从结构上可以分解成
广义表=表头+表尾
或者
广义表=子表1+子表2+···+子表n
则常用分治法求解。
例一求广义表的深度
广义表的深度=Max{子表的深度}+1
空表的深度=1
原子的深度=0
intGlistDepth（GlistL）{
//采用头尾链表存储结构,求广义表L的深度。
if（!
L）return1;//空表深度为1
if（L->tag==ATOM）return0;//原子深度为0
for（max=0,pp=L;pp;pp=pp->ptr.tp）{
dep=GlistDepth（pp->ptr.hp）;
//求以pp->ptr.hp为头指针的子表深度
if（dep>max）max=dep;
}
returnmax+1;
//非空表的深度是各子表的深度的最大值加1
}//GlistDepth
例二复制广义表
若ls=NIL则newls=NIL
否则
由表头ls^.hp复制得newhp
由表尾ls^.tp复制得newtp
构造结点newls,并使newls^.hp=newhp,
newls^.tp=newtp
StatusCopyGList（Glist&T,GlistL）{
//采用头尾链表存储结构,由广义表L复制得到
//广义表T。
if（!
L）T=NULL;//复制空表
else{
if（!
（T=（Glist）malloc（sizeof（GLNode））））
exit（OVERFLOW）;//建表结点
T->tag=L->tag;
if（L->tag==ATOM）T->atom=L->atom;
//复制单原子
else{
CopyGList（T->ptr.hp,L->ptr.hp）;
//复制广义表T->ptr.hp的一个副本L->ptr.hp
CopyGList（T->ptr.tp,L->ptr.tp）;
//复制广义表T->ptr.tp的一个副本L->ptr.tp
}//else
}//else
returnOK;
}//CopyGList
例三创建广义表的存储结构
根据LS=（1,2,,n）建广义表ls
若LS=（）则ls=NIL
否则
构造表结点ls^
分解出第一个子串1,对应建广义表的表头ls^.hp
若剩余串非空，则构造表尾结点ls^.tp
分解出第二个子串2,对应建广义表
依次类推，直至剩余串为空串止
StatusCreateGList（Glist&L,SstringS）{
//采用头尾链表存储结构，由广义表的书写形式串
//S创建广义表L。
设emp=”（）”。
if（StrCompare（S,emp））L=NULL;//创建空表
else{
if（!
（L=（Glist）malloc（sizeof（GLNode））））
exit（OVERFLOW）;//建表结点
if（StrLength（S）==1）{
L->tag=ATOM;L->atom=S
}//创建单原子广义表
else{
L->tag=LIST;p=L;
SubString（sub,S,2,StrLength（S）-2）;//脱外层括号
do{//重复建n个子表
sever（sub,hsub）;//从sub中分离出表头串hsub
CreateGList（p->ptr.hp,hsub）;q=p;
if（!
StrEmpty（sub）{//表尾不空
if（!
（p=（GLNode*）malloc（sizeof（GLNode））））
exit（OVERFLOW）;
p->tag=LIST;q->ptr.tp=p;
}
}while（!
StrEmpty（sub））;
q->ptr.tp=NULL;
}//else
}//else
returnOK;
}//CreateGList
二、后置递归法（Postponingthework）
假如某个问题的的求解过程可以分成若干步进行，并且当前这一步的解可以直接求得，则先求出当前这一步的解，对于余下的问题，若问题的性质和原问题类似，则又可递归求解。
显然，递归的终结状态应该是，当前的问题只需一步便可求得，对原问题而言，则是走到了求解的最后一步。
例一删除单链表中所有元素为x的结点
分析:
1）单链表是一种顺序结构，必须从第一个结点起，逐个检查每个结点的数据元素;
2）从另一角度看，链表又是一个递归结构，
若head是线性链表（a1,a2,,an）的头指针，
则head^.next是线性链表（a2,,an）的头指针。
voidDelete_LinearList（Link&L,Elemx）{
//删除单链表中所有元素为x的结点
if（!
L->next）{
fp=L->next;
if（fp->data==x）{
L->next=fp->next;
free（fp）;
Delete_LinearList（L,x）;
}
elseDelete_LinearList（fp,x）;
}
}//Delete_LinearList
例二删除广义表中所有元素为x的原子结点
分析:
广义表和线性表比较:
相似处:
都是顺序结构
不同处:
广义表的数据元素可能还是个广义表
voidDelete_GL（Glist&L,AtomTypex）{
//删除广义表中所有元素为x的原子结点
if（!
L->ptr.tp）{
first=L->ptr.tp;head=first->ptr.hp;
if（（head->tag==Atom）&&
（head->atom==x））{
L->ptr.tp=first->ptr.tp;free（head）;
free（first）;Delete_GL（L,x）;
}
else{
if（head->tag==LIST）
Delete_GL（head,x）;
Delete_GL（first,x）;
}
}
}//Delete_GL
例三求n个数（的不同排列）可能构成的全部序列
算法:
设序列的初始状态为空，之后从1至n逐个插入，插入的位置不同则构成不同的序列，对k,则有k个插入位置。
一般情况下的问题提法为:
假设已知含1至k-1个元素的一个排列，则需要继续从k至n逐个插入，以构成n个元素的序列。
这当前的一步是插入元素k,它可有k个插入位置。
例如，对于已经形成的序列：
1，2，，k-1，可以得到如下k个序列：
k，1，2，，k-1
1，k，2，，k-1
1，2，k，，k-1
1，2，，k-1，k
则对于已经形成的（k-1）！
个不同排列的序列，在插入k之后，得到k！
个序列。
下一步的问题就变成：
已知含1至k个元素的一个排列，需要从k+1至n逐个插入，以构成n个元素的序列。
若k=n,则表明已求得全部解。
逻辑结构采用线性表表示序列
voidPermute（List&L,intn,intk）{
//已知线性表L中已含k-1个元素，本函数将
//从k至n的元素依次插入到表中不同位置，
//以求得n个元素的所有不同排列，并输出之
for（i=1;i<=k;++i）{
ListInsert（L,i,k）;//元素k插入为第i个元素
if（k==n）ListTraverse（L,Print）;//遍历输出
elsePermute（L,n,k+1）;//继续从k+1起插入
ListDelete（L,i,e）;//删除表中当前第i个元素
}
}//Permute
主函数:
InitList（L）;
Permute（L,n,1）
以n=3为例，看图解的算法执行过程
算法执行前的初态
插入“1”之后的状态1
2112
3212312133121321
上图树中每个结点表示线性表在程序执行过程中的一个状态（如:
根结点表示算法执行前的状态；叶子结点表示插入“3”之后的状态），故称之为“状态空间树”或“递归树”。
其中，叶子结点表示“解”的状态，即“递归终结”的状态，所有非叶结点称为“活动结点”，表示求得部分解之后的状态，亦可称之为“可扩展的结点”，意为：
算法所作是“扩展”非叶结点以求得问题的一种解。
算法Permute（L,n,k）的执行过程可以看成是先根遍历这棵状态空间树，访问结点的操作是“将第k个元素插入到第i棵子树根的第i个元素之前”，然后检查是否是叶子结点，若是，则输出，否则继续依次遍历各棵子树。
注意，这棵状态空间树在“遍历”过程中动态生成和销毁，访问结点的操作实际上是生成这棵树的根结点，而遍历结束返回时，删除这棵树。
因此，问题求解的核心是分析确定状态空间树的结构，即：
从可扩展的结点扩展出的子树的状态。
在本算法的状态空间树中，第k层（遍历前的初态设为0层）的结点为插入第k个元素生成的子树根结点，因此可有k个。
类似问题很多，但对于某些问题，其状态空间树中的非叶结点不一定都是可扩展的结点，而是在求得问题的部分解之后，尚需进行检验，这类问题就是通常用“回朔法”求解的问题
三、回溯法
回溯法是一种穷举方法。
其基本思想为:
假定一个问题的解能够表示成n元组
（x1,x2,,xn）
其中xi取值于集合Si，n元组的一个子组
（x1,x2,，xi）i称为部分解，应满足一定的约束条件。
若在已求得的满足约束条件的部分解中，添加值集Si+1中的xi+1之后，仍然满足约束条件，则添加xi+1后得到一个新的部分解（x1,x2,，xi+1），之后继续添加xi+2并检查之。
若对于所有取值于集合Si+1的xi+1都不能得到新的满足约束条件的部分解（x1,x2,，xi+1），则从当前子组中删去xi,回溯到前一个部分解（x1,x2,,xi-1），重新添加那些值集Si中尚未考察过的xi，看是否满足约束条件。
如此反复进行，直至求得满足约束条件的问题的解，或者证明问题无解。
例一皇后问题求解
设四皇后问题的解为（x1,x2,x3,x4），其中xiS={1,2,3,4}
则对于每个满足约束条件的可扩充结点至多可能有四棵子树，因此它的递归状态空间树是一棵四叉树。
一般情况，对于nn的棋盘，每个满足约束条件的可扩充结点至多可能有n棵子树，即它的递归状态空间树是一棵n叉树。
voidTrial（inti,intn）{
//进入本函数时，在n×n棋盘前i-1行已放置了
//互不攻击的i-1个棋子。
现从第i行起继续为后
//续棋子选择合适位置。
当i>n时，求得一个合法
//布局，并输出之。
if（i>n）输出棋盘的当前布局；
//n为4时，即为4皇后问题
elsefor（j=1;j<=n;++j）{
在第i行第j列放置一个棋子；
if（当前布局合法）Trial（i+1,n）;
移走第i行第j列的棋子；
}
}//Trial
例二出栈序列问题
问题：
1至n的n个整数依次入栈，可能得到的出栈序列是什么？
分析:
对于栈的某个状态，只可能派生出两个状态：
一是，继续有下一个元素入栈，其前提是尚有元素还没有入栈;
二是，栈顶元素出栈，其前提是栈不空。
根据由此所画出的递归状态空间树可得下列算法：
voidS（Stack&S1,Stack&S2,Stack&S3）{
//已知三个栈的初始状态为:
S2和S3为空栈，
//栈S1中从栈顶到栈底依次存放元素1至n,
//本函数利用三个栈求得元素1至n经入栈到
//出栈可能得到的所有排列。
//递归的终结状态是S1栈和S2栈均为空栈。
ifStackEmpty（S1）&&StackEmpty（S2）
StackTraverse（S3,Print）;//输出一种排列
else{
if（!
StackEmpty（S1））{
Pop（S1,e）;Push（S2,e）;
S（S1,S2,S3）;
Pop（S2,e）;Push（S1,e）;
}
if（!
StackEmpty（S2））{
Pop（S2,e）;Push（S3,e）;
S（S1,S2,S3）;
Pop（S3,e）;Push（S2,e）;
}
}
}//S
回溯法算法的一般形式如下:
voidB（inti）{
//假设已经得到满足约束条件的部分解
//（x1,x2,，xi-1），本函数从xiSi起继续探索，
//直至求得整个解为止。
if（i>n）输出一组解（x1,x2,，xn）;
elsewhile（!
Empty（Si））{
从Si中取得xi的一个值viSi;
if（（x1,x2,，xi）满足约束条件）B（i+1）
从Si中删除vi;
}
}//B
综合几点：
1）对于含有递归特性的问题，最好设计递归形式的算法。
但也不要单纯追求形式，应在算法设计的分析过程中“就事论事”。
例如，在利用分割求解设计算法时，子问题和原问题的性质相同；或者，问题的当前一步解决之后，余下的问题和原问题性质相同，则自然导致递归求解。
2）实现递归函数，目前必须利用“栈”。
一个递归函数必定能改写为利用栈实现的非递归函数；反之，一个用栈实现的非递归函数可以改写为递归函数。
需要注意的是递归函数递归层次的深度决定所需存储量的大小。
3）分析递归算法的工具是递归树，从递归树上可以得到递归函数的各种相关信息。
例如：
递归树的深度即为递归函数的递归深度；递归树上的结点数目恰为函数中的主要操作重复进行的次数；若递归树蜕化为单支树或者递归树中含有很多相同的结点，则表明该递归函数不适用。
4）递归函数中的尾递归容易消除。
例如：
先序遍历二叉树可以改写为：
StatusPreOrderTraverse（BiTreeT,Status（Visit）（BiTreeP））{
While（T）{
if（Visit（T->data））
if（PreOrderTraverse（T->lchild））
T=T->rchild;
elsereturnERROR;
}
returnOK;
}//PreOrderTraverse
5）可以用递归方程来表述递归函数的时间性能。
例如:
假设解n个圆盘的梵塔的执行时间为T（n）
则递归方程为T（n）=2T（n-1）+C，T（0）=0
升级会员 