文档介绍：函数的递归调用与分治策略
——以C++为例
Original version by Wecan
, 2005
递归方法是算法和程序设计中的一种重要技术。递归方法即通过函数或过程调用自身将问题转化为本质相同但规中间“借助”B把金片从A移到C），再将B上的(n-1)个金片按照规则从B移到C（中间“借助”A）。
本题的特点在于不容易用数学语言写出具体的递归函数，但递归关系明显，仍可用递归方法求解。
[代码]
//
#include <>
hanoi(int n,char t1,char t2,char t3){
if (n==1)
cout<<"1 "<<t1<<" "<<t3<<endl;
else
{
hanoi(n-1,t1,t3,t2);
cout<<n<<" "<<t1<<" "<<t3<<endl;
hanoi(n-1,t2,t1,t3);
}
}
main(){
int n;
cout<<"Please enter the number of Hanoi:";
cin>>n;
cout<<"Answer:"<<endl;
hanoi(n,'A','B','C');
}
函数递归调用的应用与分治策略
许多算法都采用了分治策略求解，而可以说分治与递归是一对孪生兄弟，它们经常同时被应用于算法的设计中。下面讨论著名的Catalan数问题，人们在对它的研究中充分应用了分治策略。
[例4]Catalan数问题。
[问题描述]一个凸多边形，通过不相交于n边形内部的对角线，剖分为若干个三角形。求不同的剖分方案总数H(n)。H(n)即为Catalan数。例如，n=5时H(5)=5。
[分析]Catalan数问题有着明显的递归子问题特征。在计算Catalan数时虽然可以推导出只关于n的一般公式，但在推导过程中却要用到递归公式。下面讨论三种不同的解法，其中第三种解法没有使用递归，它是由前两种解法推导而出的。
[解法1]对于多边形V1V2…Vn，对角线V1Vi（i=3,4,…,n-1）将其分为两部分，一部分是i边形，另一部分是n-i+1边形。因此，以对角线V1Vi为一个剖分方案的剖分方案数为H(i)*H(n-i+1)。还有一种的特殊情形，是对角线V2Vn将其分为一个三角形V1V2Vn和一个n-2+1边形。为了让它同样符合粗体字给出的公式，规定H(2)=1。于是得到公式：
H(n)=∑H(i)*H(n-i+1) （i=2,3,…,n-1） ----公式(1)
H(2)=1
有了这个递归关系式，就可以用递推法或递归法解出H(n)。
[解法2]从V1向除了V2和Vn外的n-3个顶点可作n-3条对角线。每一条对角线V1Vi把多边形剖分成两部分，剖分方案数为H(i)*H(n-i+2)，由于Vi可以是V3V4…Vn-1中的任一点，且V1可换成V2，V3，…，Vn中任一点也有同样的结果。考虑到同一条对角线在2个顶点被重复计算了一次，于是对每个由顶点和对角线确定的剖分方案都乘以1/2，故有
H(n)=n∑(1/2)H(i)*H(n-i+2) （i=3,4,…,n-1）
把(1/2)提到∑外面，
H(n)=n/(2*(n-3))∑H(i)*H(n-i+2) （i=3,4,…,n-1） ----公式(2)
规定H(2)=H(3)=1，这是合理的。
由公式(2)和H(2)=1，同样可以用递推法或递归法解出H(n)。
[解法3] 把公式(1)中的自变量改为n+1，再将刚刚得出的公式(2)代入公式(1)，得到
H(n+1)=∑H(i)*H(n-i+2) （i=2,3,…,n） 由公式(1)
H(n+1)=2*H(n)+∑H(i)*H(n-i+2) （i=3,4,…,n-1） 由H(2)=1
H(n+1)=(4n-6)/n*H(n) 由公式(2)
H(n)=(4n-10)/(n-1)*H(n-1) ----公式(3)
这是一个较之前两种解法更为简单的递归公式，还可以继续简化为
H(n)=1/(n-1)*C(n-2,2n-4) ----公式(4)
这就不需要再使用递归算法了。然而在程序设计上，公式(4)反而显得更加复杂，因为要计算阶乘。因此最后给出由公式(3)作为理论依据范例程序代码。代码相当简单，这都归功于刚才的推导。如果用前两种解法中的递归关系，程序会变得复杂且容易写错。因此，有时对具体问题将递归关系公式进行必要的化简也是至关重要的。
[代码]
//
#include <>
#define MAXN 100
long f(in