|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
递归是指子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的常用方法。
|
|
|
|
递归有两个基本要素：边界条件，即确定递归到何时终止，也称为递归出口；递归模式，即大问题是如何分解为小问题的，也称为递归体。
|
|
|
|
|
|
分治法的设计思想是将一个难以直接解决的大问题分解成一些规模较小的相同问题，以便各个击破、分而治之。如果规模为n的问题可分解成k个子问题，1<k≤n，这些子问题互相独立且与原问题相同。分治法产生的子问题往往是原问题的较小模式，这就为递归技术提供了方便。
|
|
|
|
|
|
|
|
（2）求解。递归地求解各子问题。若子问题足够小，则直接求解。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
分治法也许是最广泛使用的算法设计方法，其基本思想是把大问题的解分解成一些较小的问题，然后由小问题的解方便地构造出大问题的解。
|
|
|
|
|
|
Hanoi塔问题描述如下：有n个盘子在A处，盘子从大到小，最上面的盘子最小。现在要把这n个盘子从A处搬到C处，可以在B处暂存，但任何时候都不能出现大的盘子压在小的盘子上面的情况。
|
|
|
|
当只有一个盘子时，直接从A移到C即可；如果已知n-1个盘子的移动方案，那么n个盘子的移动方案如下：先把前n-1个盘子从A借助C移动到B处，再把第n个盘子从A处直接移动到C处，然后再将B处的n-1个盘子从B处借助A处移动到C处，至此就完成了全部盘子的移动。具体C代码实现如下：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
