递归与分治的关系

任何可以用计算机求解的问题所需要的计算时间都与其规模有关。问题规模越小，解题所需要的计算时间往往也越短，从而也比较容易处理。例如，对于n个元素的排序问题，当n=1时，不需要任何计算。n=2时，只需要一次比较即可排好序。n=3时只要两次比较即可…当n较大时，问题就不那么容易处理了。要想解决一个较大的问题，有时是相当困难的。分治法的设计思想就是：将一个难以直接解决的大问题分割成一些规模较小的相同问题，以便各个击破，即分而治之。 如果原问题可分割成k个子问题，1<k<=n，且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的效小模式，这为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模不断缩小，最终使子问题缩小到容易求出其解，由此自然引出递归算法。分治和递归像一对孪生兄弟，经常同时应用在算法设计中，并由此产生许多高效算法。

递归的概念

直接或者间接地调用自身的算法称为递归算法。 用函数自身给出定义的函数称为递归函数。在计算机算法设计和分析中，递归技术是十分有用的。使用递归技术往往使函数的定义和算法的描述简捷且易于理解。有些数据结构，例如二叉树等，由于本身固有的递归特性，特别适合用递归的形式来描述。有些问题，虽然其本身并没有明显的递归结构，但用递归技术来求解，可以使设计出的算法简捷且易于分析。例如：

1. 阶乘函数。阶乘函数可递归定义为n!=n*(n-1)!，当n=0时n！=1。则递归计算如下：

int jiecheng(int n )
{if(n==0)return 1;return n*jiecheng(n-1);
}

2. Fibonacci数列
   F(0)=0
   F(1)=1
   F(n)=F(n−1)+F(n−2) ,(n≥2,n∈N)
   递归表达为：

int Fibonacci(int n)
{if( n == 0 ) return 0;if( n == 1 ) return 1;return Fibonacci(n - 1) + Fibonacci(n - 2);
}

3. 汉诺塔问题
   递归表达为：

void hanoi(int n,int a,int b,int c){
if(n>0){       hanoi(n-1, a, c, b);将n-1个盘子由a移动到b，以c为辅助柱子move(a,c);将a上的最后一个盘子移动到chanoi(n-1, b, a, c);将n-1个盘子由b移动到c，以a为辅助柱子}
}

实现这种递归调用的关键是为算法建立递归调用工作栈。通常，在一个算法中调用另外一个算法时，系统需在运行被调用算法之前先完成三件事：（1）将所有实参指针、返回地址等信息传递给被调用算法；（2）为被调用算法的局部变量分配存储区；（3）将控制转移到被调用算法的人口。
在从被调用算法返回调用算法时，系统相应地要完成三件事：（1）保存被调用算法的计算结果；（2）释放分配给被调用算法的数据区；（3）依照被调用算法保存的返回地址将控制转移到调用算法。

当有多个算法构成嵌套调用时，按照“后调用先返回”的原则进行。上述算法之间的信息传递和控制转移必须通过栈来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每调用一个算法，就为它在栈顶分配一个存储区，每退出一个算法，就释放它在栈顶的存储区。当前正在运行的算法的数据一定在栈顶。

递归算法的实现类似于多个算法的嵌套调用，只是调用算法和被调用算法是同一个算法。因此，与每次调用相关的一个重要概念是递归算法的调用层次。若调用一个递归算法的主算法为第0层算法，则从主算法调用递归算法为进入第1层调用；从第i层递归调用本算法为进入第i+1层调用。反之，退出第i层递归调用，则返回至第i-1层调用。为了保证递归调用正确执行，系统需要建立一个递归调用工作栈，为各层次的调用分配数据存储区。每层递归调用所需的信息构成一个工作记录，其中包括所有实参指针、所有局部变量以及返回上一层的地址。每进入一层递归调用，就产生一个新的工作记录压入栈顶。每退出一层递归调用，就从栈顶弹出一个工作记录。

由于递归算法结构清晰，可读性强，且容易用数学归纳法证明算法的正确性，因此它为设计算法、调试程序带来很大方便。然而，递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。若在程序中消除算法的递归调用，则其运行时间可大为节省。因此，有时希望在递归算法中消除递归调用，使其转化为一个非递归算法。通常，消除递归采用一个用户定义的栈来模拟系统的递归调用工作栈，从而达到将递归算法改为非递归算法的目的。还可以用递推实现递归函数以及通过变换能将一些递归转化为尾递归，从而迭代求出结果。 仅仅是机械地模拟还不能达到缩短计算时间和减少存储空间的目的，还需要根据具体程序的特点对递归调用工作栈进行简化，尽量减少栈操作，压缩栈存储空间以达到节省计算时间和存储空间的目的。

分治法的基本思想

分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。它的一般算法设计模式如下：

divide-and-conquer（p）{if（|p|<=n0）adhoc（p）；divide p into smaller subinstances p1，p2，...pk；for（int i=1；i<=k;i++）{yi=divide-and-conquer(pi);}return mergr(y1,y2,....,yk);
}

其中，|p|表示问题P的规模，n0为以阈值，表示当问题P的规模不超过n0时，问题容易解出，不必要再继续分解。adhoc（p）是该分治法中的基本子算法，用于直接解小规模的问题P。当P的规模不超过n0时，直接用算法adhoc（p）求解。算法merge（y1，y2，…，yk）是该分治法中的合并子算法，用于将P的子问题P1，P2,…,PK的解y1，y2，…，yk合并为P的解。

根据分治法的分割原则，应把原问题分为多少个子问题才较适宜？每个子问题是否规模相同或者咋样才为适当？这些问题很难一概而论。但从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同，即将一个问题分为大小相等的k个子问题的处理方法是行之有效的。许多问题可以取k=2.这种使子问题规模大致相等的做法出自一种平衡子问题的思想，几乎总是比子问题规模不等的做法要好。

从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法，因此分治法的计算效率通常可以 用递归方程来进行分析。一个分治法将规模为n的问题分为k个规模为n/m的子问题去解。将原问题分解为k个子问题及用merge将k个子问题的解合并为原问题的解需用f（n）单位时间。如果T（n）表示该分治法divide-and-conquer（p）解规模为|P|=n的问题所需要的计算时间，则

T(n)=O(1),         n=1
T(n)=kT(n/m)+f(n), n>1