成对递归算法

‘壹’ 请问递归算法的时间复杂度如何计算呢

递归算法的时间复杂度在算法中，当一个算法中包含递归调用时，其时间复杂度的分析会转化为一个递归方程求解，常用以下四种方法：

1.代入法(Substitution Method)

代入法的基本步骤是先推测递归方程的显式解，然后用数学归纳法来验证该解是否合理。

2.递归程序设计是程序设计中常用的一种方法，它可以解决所有有递归属性的问题，并且是行之有效的.

3.但对于递归程序运行的效率比较低，无论是时间还是空间都比非递归程序更费，若在程序中消除递归调用，则其运行时间可大为节省.

‘贰’ 常见算法1——递归算法

递归算法就是通过自身不断反复调用自身以解决问题，其中最经典的也就是汉诺达和斐波纳契数列的问题了。
1.汉诺塔问题
在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片，一次只移动一片，不管在哪根针上，小片必在大片上面。当所有的金片都从梵天穿好的那根针上移到另外一概针上时，世界就将在一声霹雳中消灭，梵塔、庙宇和众生都将同归于尽。

分析：挪到C的金片也是从下到上由大到小的顺序排列，那么A之剩下最下面的金片移动到C的时候，C上面是不可以有金片的，这个时候A上面只有第n个金片，B上面有n-1个金片，C上面没有金片，然后这个情况就和刚开始情况相同了，只不过A和B颠倒了位置而已。
（1）n-1个金片从A通过C移动到B，n-1个金片从A通过C移动到B也是不断调用自身逐步缩小范围。通过递归调用后，就完成了A上面仅剩下最大的金片，C上面没有金片，B上面有n-1个金片。
（2）最大的那个金片从A移动到C
（3）调用自身重复刚开始的情况，只不过现在有金片的是B，即B通过A把金片移动到C。

2.斐波纳契数列
2.1生兔子问题
古典问题：3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？下面先从小到大分析下这个情况
分析：假设将兔子分为小中大三种，兔子从出生后从第三个月开始每个月就会生出一对兔子，也就是一旦兔子变为大兔子那么他就生了一对兔子
分析情况图如下

很明显这个是一个为斐波那契数列，即如果用f(n)表示第n个月的兔子的对数，那么f(n)=f(n-1)+f(n-2)

2.2走台阶问题
一个台阶总共有n级，如果一次可以跳1级，也可以跳2级。求总共有多少总跳法，并分析算法的时间复杂度。
分析：假设我们现在还有最后一步要走，可能的情况有哪些？
（1）我们站在第9级上，一步1级后到达顶端；
（2）我们站在第8级上，一步2级后到达顶端；
所以，最后一步可以走1级或者2级，不外乎两种情况。
再假设，已知从0级到9级的走法有M种，从0级到8级的走法有N种，那么从0到10级的走法和M、N有什么关系呢？从0到10级的走法一共是多少种呢？答案是M+N。
所以逐步递归，说白了，这还是个Fibnacci数列。即f(n)=f(n-1)+f(n-2)，事件复杂度是2^n

台阶问题的变种:
一个台阶总共有n级，如果一次可以跳1级，也可以跳2级.....也可以跳n级。求总共有多少总跳法

分析：用Fib(n)表示跳上n阶台阶的跳法数。如果按照定义，Fib(0)肯定需要为0，否则没有意义。但是我们设定Fib(0) = 1；n = 0是特殊情况，通过下面的分析就会知道，强制令Fib(0) = 1很有好处。因为Fib(0)等于几都不影响我们解题，但是会影响我们下面的分析理解。

当n = 1 时， 只有一种跳法，即1阶跳：Fib(1) = 1;

当n = 2 时， 有两种跳的方式，一阶跳和二阶跳：Fib(2) = 2;

到这里为止，和普通跳台阶是一样的。

当n = 3 时，有三种跳的方式，第一次跳出一阶后，对应Fib(3-1)种跳法； 第一次跳出二阶后，对应Fib(3-2)种跳法；第一次跳出三阶后，只有这一种跳法。Fib(3) = Fib(2) + Fib(1)+ 1 = Fib(2) + Fib(1) + Fib(0) = 4;

当n = 4时，有四种方式：第一次跳出一阶，对应Fib(4-1)种跳法；第一次跳出二阶，对应Fib(4-2)种跳法；第一次跳出三阶，对应Fib(4-3)种跳法；第一次跳出四阶，只有这一种跳法。所以，Fib(4) = Fib(4-1) + Fib(4-2) + Fib(4-3) + 1 = Fib(4-1) + Fib(4-2) + Fib(4-3) + Fib(4-4) 种跳法。

当n = n 时，共有n种跳的方式，第一次跳出一阶后，后面还有Fib(n-1)中跳法； 第一次跳出二阶后，后面还有Fib(n-2)中跳法..........................第一次跳出n阶后，后面还有 Fib(n-n)中跳法。Fib(n) = Fib(n-1)+Fib(n-2)+Fib(n-3)+..........+Fib(n-n) = Fib(0)+Fib(1)+Fib(2)+.......+Fib(n-1)。

通过上述分析，我们就得到了通项公式：

因此，有 Fib(n-1)=Fib(0)+Fib(1)+Fib(2)+.......+Fib(n-2)

两式相减得：Fib(n)-Fib(n-1) = Fib(n-1) =====》 Fib(n) = 2*Fib(n-1) n >= 3

这就是我们需要的递推公式：Fib(n) = 2*Fib(n-1) n >= 3

‘叁’ 递归的原理解释

递归的原理解释：
递归，是函数实现的一个很重要的环节，很多程序中都或多或少的使用了递归函数。递归的意思就是函数自己调用自己本身，或者在自己函数调用的下级函数中调用自己。
递归之所以能实现，是因为函数的每个执行过程都在栈中有自己的形参和局部变量的拷贝，这些拷贝和函数的其他执行过程毫不相干。这种机制是当代大多数程序设计语言实现子程序结构的基础，是使得递归成为可能。假定某个调用函数调用了一个被调用函数，再假定被调用函数又反过来调用了调用函数。这第二个调用就被称为调用函数的递归，因为它发生在调用函数的当前执行过程运行完毕之前。而且，因为这个原先的调用函数、现在的被调用函数在栈中较低的位置有它独立的一组参数和自变量，原先的参数和变量将不受影响，所以递归能正常工作。程序遍历执行这些函数的过程就被称为递归下降。
程序员需保证递归函数不会随意改变静态变量和全局变量的值，以避免在递归下降过程中的上层函数出错。程序员还必须确保有一个终止条件来结束递归下降过程，并且返回到顶层。

‘肆’ 《算法导论》三种解递归式的方法

代入法可以用来确定一个递归式的上界或下界。这种方法很有效，但只能用于解的形式很容易猜的情形。

例如，我们需要确定下面递归式的上界：

该递归式与归并排序相似，我们可以猜测其解为

代入法要求证明，恰当选择常数 c>0，可有 T(n)≤cn lgn。首先假设此上界对所有正数 m<n 都成立，特别是对于 m=n/2，有 T(n/2)≤c(n/2)lg(n/2)。将其代入递归式，得到：

其中，只要 c≥1，最后一步都会成立。

并不存在通用的方法来猜测递归式的正确解，但总有一些试探法可以帮助做出好的猜测：

如果某个递归式与先前见过的类似，则可猜测该递归式有类似的解。如，递归式

看起来比较难解，因为右式 T 的自变量中加了 17，但我们可以猜测这个多出来的项对解的影响不大，因为当 n 很大时， 与 之间的差别并不大，两者都将 n 分成均匀的两半。

另一种方法是先证明递归式的较松的上下界，然后再缩小不确定性区间。例如，对递归式 ，因为递归式中有 n，而我们可以证明初始上界为 。然后，逐步降低其上界，提高其下界，直到达到正确的渐近确界 。

有时，我们或许能够猜出递归式解的渐近界，但却会在归纳证明时出现一些问题。通常，问题出在归纳假设不够强，无法证明其准确的界，遇到这种情况时，可以去掉一个低阶项来修改所猜测的界，以使证明顺利进行。如下面的递归式：

可以猜测其解为 ，即要证明对适当选择的 c，有 。有所猜测的界对递归式做替换，得到

由此无法得到 ，无论 c 的值如何。如果猜测一个更大的界，如 ，虽然这确实是上界，但事实上，所猜测的解 却是正确的。为了证明这一点，要做一个更强的归纳假设。

从直觉上说，猜测 几乎是正确的，只是差了一个常数 1，即一个低阶项，然而，就因为差了一项，数学归纳法就无法证明出期望的结果。从所作的猜测中减去一个低阶项，即 是个常数。现在有

只要 b≥ 1。这里，c 要选的足够大，以便能处理边界条件。

你可能会觉得从所作的猜测中减去一项有点儿与直觉不符。为什么不是增加一项来解决问题呢？关键在于要理解我们是在用数学归纳法：通过对更小的值作更强的假设，就可以证明对某个给定值的更强的结论。

在运用渐近表示时很容易出错。例如，对递归式 ，由假设 ，并证明

就是错误的，因为 c 是常数，因而错误地证明了 。错误在于没有证明归纳假设的准确形式，即 。

有时，对一个陌生的递归式作一些简单的代数变换，就会使之变成读者较熟悉的形式。如下例子：

这个式子看上去比较难，但可以对它进行简化，方法是改动变量。为了方便起见，不考虑数的截取整数问题，如将 化为整数。设 ，得

再设 ，得到新的递归式

这个式子看起来与 就非常像了，这个新的递归式的界是： 。将 带回 ，有 。

有时候，画出一个递归树是一种得到好猜测的直接方法。在递归树中，每一个节点都代表递归函数调用集合中一个子问题的代价。将树中每一层内的代价相加得到一个每层代价的集合，再将每层的代价相加，得到的结果是所有层次的总代价。当用递归式表示分治算法的运行时间时，递归树的方法尤其有用。

递归树最适合用来产生好的猜测，然后用代入法加以验证。但使用递归树产生好的猜测时，通常可以容忍小量的“不良量”，因为稍后就会证明所做的猜测。如果画递归树时非常地仔细，并且将代价都加了起来，那么就可以直接用递归树作为递归式的解的证明。

在讲述例子之前，我们先来看一个几何级数公式

对于实数 x≠1，式

是一个几何级数（或称指数级数），其值为

当和是无限的且 |x|<1 时，有无限递减几何级数

我们以递归式

为例来看一下如何用递归树生成一个好的猜测。首先关注如何寻找解的一个上界，因为我们知道舍入对求解递归式通常没有影响（此处即是我们需要忍受不精确的一个例子），因此可以为递归式

创建一颗递归树，其中已将渐近符号改写为隐含的常数系数 c>0。

构造的递归树如下：

求所有层次的代价之和，确定整棵树的代价：

最后的这个公式看起来不够整洁，但我们可以再次充分利用一定程度的不精确，并利用无限递减几何级数作为上界。回退一步，得到：

此时，我们得到了递归式的一个猜测，在上面的例子里， 系数形成了一个递减的等比级数，可知这些系数的总和的上界是常数 。由于树根所需的代价为 ，所以根部的代价占总代价的一个常数部分。换句话说，整棵树的总代价是由根部的代价所决定的。

事实上，如果 确实是此递归式的上界，那么它一定是确界，为什么呢？第一个递归调用所需要的代价是 ，所以 一定是此递归式的下界。

现在我们可以使用代换法来验证猜测的正确性， 是递归式 的一个上界。只需要证明，当某常数 d>0， 成立。适用与前面相同的常数 c>0，有

只要 d≥ ，最后一步都会成立。

上图是递归式

对应的递归树。我们还是使用 c 来代表 项常数因子。当将递归树内各层的数值加起来时，可以得到每一层的 cn 值。从根部到叶子的最长路径是 。因为当 时， ，所以树的深度是 。

直觉上，我们预期递归式的解至多是层数乘以每层的代价，也就是 。总代价被均匀地分布到递归树内的每一层上。这里还有一个复杂点：我们还没有考虑叶子的代价。如果这棵树是高度为 的完整二叉树，那么有 个叶子节点。由于叶子代价是常数，因此所有叶子代价的总和为 ，或者说 。然而，这棵递归树并不是完整的二叉树，少于 个叶子，而且从树根往下的过程中，越来越多的内部结点在消失。因此，并不是所有层次都刚好需要 cn 代价；越靠近底层，需要的代价越少。我们可以计算出准确的总代价，但记住我们只是想要找出一个猜测来使用到代入法中。让我们容忍这些误差，而来证明上界为 的猜测是正确的。

事实上，可以用代入法来证明 是递归式解的上界。下面证明 ，当 d 是一个合适的正值常数，则

上式成立的条件是 。因此，没有必要去更准确地计算递归树中的代价。

主方法给出了求解递归式的“食谱”方法，即将规模为 n 的问题划分为 a 个子问题的算法的运行时间，每个子问题规模为 ，a 和 b 是正常数。a 个子问题被分别递归地解决，时间各为 。划分原问题和合并答案的代价由函数 描述。

从技术正确性角度来看，递归式实际上没有得到很好的定义，因为 可能不是一个整数。但用 向上取整或向下取整来代替 a 项 并不影响递归式的渐近行为，因而，在写分治算法时略去向下取整和向上取整函数会带给很大的方便。

其中我们将 n/b 解释为 n 除以 b 的向下取整或向上取整。那么 T(n) 有如下渐近界：

在使用主定理之前，我们需要花一点时间尝试理解它的含义。对于三种情况的每一种，将函数 f(n) 与函数 进行比较。直觉上，两个函数较大者决定了递归式的解。若函数 更大，如情况 1，则解为 T(n)= ( )。若函数 f(n) 更大，如情况 3，则解为 T(n)= (f(n))。若两个函数大小相当，如情况 2，则乘上一个对数因子，解为 T(n)= ( )= ( )。

另外还有一些技术问题需要加以理解。在第一种情况下，不仅要有 小于 ，还必须是多项式地小于，也就是说， 必须渐近小于 ，要相差一个因子 ，其中 是大于 0 的常数。在第三种情况下，不是 大于 就够了，而是要多项式意义上的大于，而且还要满足“正则”条件 。

注意：三种情况并没有覆盖所有可能的 f(n)。当 f(n) 只是小于 但不是多项式地小于时，在第一种情况和第二种情况之间就存在一条“沟”。类似情况下，当 f(n) 大于 ，但不是多项式地大于时，第二种情况和第三种情况之间就会存在一条“沟”。如果 f(n) 落在任一条“沟”中，或是第三种情况种规则性条件不成立，则主方法就不能用于解递归式。

使用主方法很简单，首先确定主定理的哪种情况成立，即可得到解。

例如：

对于这个递归式，我们有 a=9，b=3，f(n)=n，因此 = = 。由于 f(n) = ，其中 ， 因此可以应用于主定理的情况 1，从而得到解 T(n) = Θ( ) 。

现在考虑

其中，a = 1， b = 3/2， f(n) = 1，因此 = = = 1 。由于 f(n) = = Θ(1) ，因此可应用于情况2，从而得到解 T(n) = Θ( ) 。

对于递归式

我们有 a = 3，b = 4，f(n) = nlgn，因此 = =O( )。由于 当 n，其中 ，因此，如果可以证明正则条件成立，即应用于情况 3。当 n 足够大时，对于 ， ，因此，由情况 3，递归式的解为 T(n)= ( )。

主方法不能用于如下递归式：

虽然这个递归式看起来有恰当的形式：a=2，b=2， ，以及 。你可能错误地认为应该应用情况 3，因为 渐近大于 。问题出现在它并不是多项式意义上的大于。对任意正常数 ，比值 都渐近小于 。因此，递归式落入了情况 2 和情况 3 之间的间隙。

证明分为两部分。第一部分分析“主”递归式 ，并作了简化假设 仅定义在 b>1 的整数幂上，即 ， ， ，…。这部分从直觉上说明该定理为什么是正确的。第二部分说明如何将分析扩展至对所有的正整数 n 都成立，主要是应用数学技巧来解决向下取整函数和向上取整函数的处理问题。

取正合幂时的证明

对于递归式

此时的假设是 n 为 b>1 的正合幂，且 b 不必是整数。分析可分成三个引理说明，第一个引理是将解原递归式的问题归约为对一个含和式的求值的问题。第二个引理决定含和式的界，第三个引理把前两个合在一起，证明当 n 为 b 的正合幂时主定理成立。

引理一 ：设 a≥1，b>1 为常数，f(n) 为定义在 b 的正合幂上的非负函数。定义 如下：

其中 i 是正整数，则有

证明：如下图。根节点代价为 f(n)，它有 a 个子女，每个代价是 。（为方便起见可将 a 视为整数，但这对数学推导没什么影响。）每个子女又各有 a 个子女，代价为 。这样就有 个结点离根的距离为 2。一般地，距根为 j 的结点有 个，每一个的代价为 。每一个叶结点的代价为 ，每一个都距根 ，因为 。树中共有 个叶结点。

可以将树中各层上的代价加起来而得到方程 ，第 j 层上内部结点的代价为 ，故各层内部结点的总代价和为

在其所基于的分治算法中，这个和值表示了将问题分解成为子问题并将子问题的解合并时所花的代价，所有叶子的代价（即解 个规模为 1 的子问题的代价）为 。

根据递归树，主定理的三种情况对应于树中总代价的三种情况：1、由所有叶子节点的代价决定；2、均匀分布在各层上；3、由根结点的代价决定。

引理二 ：设 a≥1，b≥1 为常数， 为定义在 b 的整数幂上的非负函数。函数 由下式定义

对 b 的整数幂，该函数可被渐近限界为：

证明：对情况 1，有 ，这隐含着 。用它对方程 做代换，得

对 O 标记内的式子限界，方法是提出不变项并作简化，得到一个上升几何级数：

因为 b 与 都是常数，最后的表达式可化简为 。用此表达式对 作替换，得

情况 1 得以验证。

为证情况 2，假设 ，有 。用此式对方程 作替换，得

对 记号中的式子做类似情况 1 中的限界，但所得并非是几何级数，而是每项都是相同的:

用此方程对 中的和式做替换，有

则情况 2 得以验证。情况 3 也可以用类似的方式证明。

引理三 ：设 a≥1，b>1 是常量， 是定义在 b 的整数幂上的非负函数。定义 T(n) 如下：

其中 i 是正整数。对于 b 的整数幂，T(n) 可有如下渐近界：

证明：用引理二给出的界来对引理一中的式 求值。对情况 1 有

对情况 2 有

对情况 3 有

‘伍’ 设计递归算法生成n个元素的所有排列对象

#include<iostream>
#include<iterator>
#include<algorithm>
using namespace std;

template<class T>
void permutation(T list[], int k, int m)
{
if (k == m)
{
(list, list + m + 1, ostream_iterator<T>(cout, "")); //将当前list排序
cout << endl;
}
else{
for (int i = k; i <= m; i++)
{
swap(list[i], list[k]); //将下标为i的元素交换到k位置，类似从list[k:m]中剔除操作
permutation(list, k + 1, m);
swap(list[i], list[k]);
}
}
}

int main(int argc, char* argv[])
{
char arr[3] = { 'a', 'b', 'c' };
cout << "排序结果如下：" << endl;
permutation(arr, 0, 2);
return 0;

}

(5)成对递归算法扩展阅读

递归，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。也就是说，递归算法是一种直接或者间接调用自身函数或者方法的算法。

通俗来说，递归算法的实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法来表示问题的解。

递归的基本原理

第一：每一级的函数调用都有自己的变量。

第二：每一次函数调用都会有一次返回。

第三：递归函数中，位于递归调用前的语句和各级被调用函数具有相同的执行顺序。

第四：递归函数中，位于递归调用后的语句的执行顺序和各个被调用函数的顺序相反。

第五：虽然每一级递归都有自己的变量，但是函数代码并不会得到复制。

‘陆’ 设计递归算法生成n个元素的所有排列对象

#include<iostream>
#include<cmath>
using namespace std;

int count(int n)

//算n的阶乘——因为n个数能组成n!个数
{

if(n<1)

{

cout<<"输入也错！";

exit(0);

}

else

if(n==1)

return 1;

else

return count(n-1)*n;
}

int pow10(int n)
//算出10的n次方
{

int a;

if(n==0)

return 1;

else

for(int i=1;i<=n;i++)

a=10*pow10(n-1);

return a;
}
int * comm(int n)

//组合n!个数（这里用递归算）
{

int *a=new int[count(n)];

if(count(n)==1)

a[0]=1;

else

{

int *b=new int[count(n-1)];

b=comm(n-1);

for(int i=0;i<count(n-1);i++)

for(int j=0;j<n;j++)

a[i*n+j]=(b/pow10(j)*10+n)*pow10(j)+b%pow10(j);

}

return a;
}
void main()
{

int n;

cout<<"请输入n=";

cin>>n;

int *a=new int[count(n)];

a=comm(n);

cout<<"1-"<<n<<"自然数所有的排列组合为：\
";

for(int i=0;i<count(n);i++)

cout<<a<<" ";
}

=======================================
#define MAX 1000
#include<stdio.h>

void DispArrangement(int a[MAX], int n, int deepth)
{

int i, temp;

if(deepth == 1) {

for(i = 1; i <= n; i ++) {

printf("%d", a);

}

printf("\
");

} else {

for(i = 1; i <= deepth; i ++ ){

temp = a[n - deepth + 1];

a[n - deepth + 1] = a[n - deepth + i];

a[n - deepth + i] = temp;

DispArrangement(a, n, deepth - 1);

temp = a[n - deepth + 1];

a[n - deepth + 1] = a[n - deepth + i];

a[n - deepth + i] = temp;

}

}
}

int main(void)
{

int i, n, a[MAX];

scanf("%d", &n);

for(i = 1; i <= n; i ++ ) {

a = i;

}

DispArrangement(a, n, n);

return 0;
}

‘柒’ 请教高人 递归算法编写思路技巧

一个子程序（过程或函数）的定义中又直接或间接地调用该子程序本身，称为递归。递归是一种非常有用的程序设计方法。用递归算法编写的程序结构清晰，具有很好的可读性。递归算法的基本思想是：把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。规模较小的问题又变成规模更小的问题，并且小到一定程度可以直接得出它的解，从而得到原来问题的解。
利用递归算法解题，首先要对问题的以下三个方面进行分析：
一、决定问题规模的参数。需要用递归算法解决的问题，其规模通常都是比较大的，在问题中决定规模大小（或问题复杂程度）的量有哪些？把它们找出来。
二、问题的边界条件及边界值。在什么情况下可以直接得出问题的解？这就是问题的边界条件及边界值。
三、解决问题的通式。把规模大的、较难解决的问题变成规模较小、易解决的同一问题，需要通过哪些步骤或等式来实现？这是解决递归问题的难点。把这些步骤或等式确定下来。
把以上三个方面分析好之后，就可以在子程序中定义递归调用。其一般格式为：
if 边界条件 1 成立 then
赋予边界值 1
【 elseif 边界条件 2 成立 then
赋予边界值 2
┇ 】
else
调用解决问题的通式
endif
例 1 ： 计算勒让德多项式的值

x 、 n 由键盘输入。
分析： 当 n ＝ 0 或 n ＝ 1 时，多项式的值都可以直接求出来，只是当 n ＞ 1 时，才使问题变得复杂，决定问题复杂程度的参数是 n 。根据题目提供的已知条件，我们也很容易发现，问题的边界条件及边界值有两个，分别是：当 n ＝ 0 时 P n (x) ＝ 1 和当 n ＝ 1 时 P n (x) ＝ x 。解决问题的通式是：
P n (x) ＝ ((2n － 1)P n － 1 (x) － (n － 1)P n － 2 (x)) ／ n 。
接下来按照上面介绍的一般格式定义递归子程序。
function Pnx(n as integer)
if n ＝ 0 then
Pnx ＝ 1
elseif n ＝ 1 then
Pnx ＝ x
else
Pnx ＝ ((2*n － 1)*Pnx(n － 1) － (n － 1)*Pnx(n － 2)) ／ n
endif
end function
例 2 ： Hanoi 塔问题：传说印度教的主神梵天创造世界时，在印度北部佛教圣地贝拿勒斯圣庙里，安放了一块黄铜板，板上插着三根宝石针，在其中一根宝石针上，自下而上地放着由大到小的 64 个金盘。这就是所谓的梵塔（ Hanoi ），如图。梵天要求僧侣们坚持不渝地按下面的规则把 64 个盘子移到另一根针上：

(1) 一次只能移一个盘子；
(2) 盘子只许在三根针上存放；
(3) 永远不许大盘压小盘。
梵天宣称，当把他创造世界之时所安放的 64 个盘子全部移到另一根针上时，世界将在一声霹雳声中毁灭。那时，他的虔诚的信徒都可以升天。
要求设计一个程序输出盘子的移动过程。
分析： 为了使问题更具有普遍性，设共有 n 个金盘，并且将金盘由小到大依次编号为 1 ， 2 ，…， n 。要把放在 s(source) 针上的 n 个金盘移到目的针 o(objective) 上，当只有一个金盘，即 n ＝ 1 时，问题是比较简单的，只要将编号为 1 的金盘从 s 针上直接移至 o 针上即可。可定义过程 move(s,1,o) 来实现。只是当 n>1 时，才使问题变得复杂。决定问题规模的参数是金盘的个数 n ；问题的边界条件及边界值是：当 n ＝ 1 时， move(s,1,o) 。
当金盘不止一个时，可以把最上面的 n － 1 个金盘看作一个整体。这样 n 个金盘就分成了两个部分：上面 n － 1 个金盘和最下面的编号为 n 的金盘。移动金盘的问题就可以分成下面三个子问题（三个步骤）：
(1) 借助 o 针，将 n － 1 个金盘（依照上述法则）从 s 针移至 i(indirect) 针上；
(2) 将编号为 n 的金盘直接从 s 针移至 o 针上；
(3) 借助 s 针，将 i 针上的 n － 1 个金盘（依照上述法则）移至 o 针上。如图

其中第二步只移动一个金盘，很容易解决。第一、第三步虽然不能直接解决，但我们已经把移动 n 个金盘的问题变成了移动 n － 1 个金盘的问题，问题的规模变小了。如果再把第一、第三步分别分成类似的三个子问题，移动 n － 1 个金盘的问题还可以变成移动 n － 2 个金盘的问题，同样可变成移动 n － 3 ，…， 1 个金盘的问题，从而将整个问题加以解决。
这三个步骤就是解决问题的通式，可以以过程的形式把它们定义下来：
hanoi(n － 1,s,o,i)
move(s,n,o)
hanoi(n － 1,i,s,o)
参考程序如下：
declare sub hanoi(n,s,i,o)
declare sub move(s,n,o)
input "How many disks?",n
s ＝ 1
i ＝ 2
o ＝ 3
call hanoi(n,s,i,o)
end
sub hanoi(n,s,i,o)
rem 递归子程序
if n ＝ 1 then
call move(s,1,o)
else
call hanoi(n － 1,s,o,i)
call move(s,n,o)
call hanoi(n － 1,i,s,o)
endif
end sub
sub move(s,n,o)
print "move disk";n;
print "from";s;"to";o
end sub

‘捌’ 什么是递推法和递归法

问题一：什么是递推法和递归法?两者在思想有何联系 程序调用自身的编程技巧称为递归。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
递推算法是一种用若干步可重复的简运算（规律）来描述复杂问题的方法。递推是序列计算机中的一种常用算法。它是按照一定的规律来计算序列中的每个项，通常是通过计算机前面的一些项来得出序列中的指定象的值。
迭代是重复反馈过程的活动，其目的通常是为了逼近所需目标或结果。每一次对过程的重复称为一次“迭代”，而每一次迭代得到的结果会作为下一次迭代的初始值。

问题二：递推和递归算法有什么区别 递归指自我调用的函数，自己调用自己；递推指重复进行的过程，重复进行一个过程，

问题三：的递推和递归方法的区别是什么 递归就是自己调用自己吧！
递推是从头向后推吧！

问题四：递推和递归算法有什么区别 递归就是自己调用自己吧！
递推是从头向后推吧！

问题五：递推和递归的区别是什么 1.递归：将问题规模为n的问题，降解成若干个规模为n-1的问题，依次降解，直到问题规模可求，求出低阶规模弯中的解，代入高阶问题中，直至求出规模为n的问题的解。
2.递推：构造低阶的规模(如规模为i，一般i=0)的问题，并求出解，推导出问题规模为i+1的问题以及解，依次推到规模为n的问题。
3.递归包括回溯和递推两个过程。
最好的例子是斐波那契数列: 1 1 2 3 5 8 13 21 ... ...
总结成公式就是F(n+1)=F(n)+F(n-1), F(0)=F(1)=1;
你可以用递归的方法写这个函数:
int F(int n) {
if (n 问题六：递推算法和递归算法有什么区别 递推就是从前往后推,递归还有个回溯的过程
举个例子,数列:1,1,2,3,5,8,13,21,……
要求第100项,就得从前两项开始推,直到第100项,是一个递推的过程
f[0]=f[1]=1;
for(i=2;i 问题七：递推法和递归法两者在思想有何联系 两者是一样的，没有本质区别。

问题八：递推算法的递推与递归的世槐比较 相对于递归算法,递推算法免除了数据埋返山进出栈的过程，也就是说,不需要函数不断的向边界值靠拢,而直接从边界出发,直到求出函数值.比如阶乘函数：f(n)=n*f(n-1)在f(3)的运算过程中,递归的数据流动过程如下:f(3){f(i)=f(i-1)*i}-->f(2)-->f(1)-->f(0){f(0)=1}-->f(1)-->f(2)--f(3){f(3)=6}而递推如下:f(0)-->f(1)-->f(2)-->f(3)由此可见,递推的效率要高一些,在可能的情况下应尽量使用递推.但是递归作为比较基础的算法,它的作用不能忽视.所以,在把握这两种算法的时候应该特别注意。 所谓顺推法是从已知条件出发，逐步推算出要解决的问题的方法叫顺推。如斐波拉契数列，设它的函数为f(n),已知f(1)=1，f(2)=1;f(n)=f(n-2)+f(n-1)(n>=3,n∈N)。则我们通过顺推可以知道,f(3)=f(1)+f(2)=2,f(4)=f(2)+f(3)=3……直至我们要求的解。 所谓逆推法从已知问题的结果出发，用迭代表达式逐步推算出问题的开始的条件，即顺推法的逆过程，称为逆推。

问题九：什么是递归算法 递归算法就是一个函数通过不断对自己的调用而求得最终结果的一种思维巧妙但是开销很大的算法。
比如：
汉诺塔的递归算法：
void move(char x,char y){
printf(%c-->%c\n,x,y);
}
void hanoi(int n,char one,char two,char three){
/*将n个盘从one座借助two座，移到three座*/
if(n==1) move(one,three);
else{
hanoi(n-1,one,three,two);
move(one,three);
hanoi(n-1,two,one,three);
}
}
main(){
int n;
printf(input the number of diskes:);
scanf(%d,&n);
printf(The step to moving %3d diskes:\n,n);
hanoi(n,'A','B','C');
}
我说下递归的理解方法
首先：对于递归这一类函数，你不要纠结于他是干什么的，只要知道他的一个模糊功能是什么就行，等于把他想象成一个能实现某项功能的黑盒子，而不去管它的内部操作先，好，我们来看下汉诺塔是怎么样解决的
首先按我上面说的把递归函数想象成某个功能的黑盒子，void hanoi(int n,char one,char two,char three); 这个递归函数的功能是：能将n个由小到大放置的小长方形从one 位置，经过two位置 移动到three位置。那么你的主程序要解决的问题是要将m个的汉诺块由A借助B移动到C，根据我们上面说的汉诺塔的功能，我相信傻子也知道在主函数中写道：hanoi(m,A,B,C)就能实现将m个块由A借助B码放到C，对吧？所以，mian函数里面有hanoi(m,'A','C','B');这个调用。
接下来我们看看要实现hannoi的这个功能，hannoi函数应该干些什么？
在hannoi函数里有这么三行
hanoi(n-1,one,three,two);
move(one,three);
hanoi(n-1,two,one,three);
同样以黑盒子的思想看待他，要想把n个块由A经过B搬到C去，是不是可以分为上面三步呢？
这三部是：第一步将除了最后最长的那一块以外的n-1块由one位置经由three搬到two 也就是从A由C搬到B 然后把最下面最长那一块用move函数把他从A直接搬到C 完事后 第三步再次将刚刚的n-1块借助hanno处函数的功能从B由A搬回到C 这样的三步实习了n块由A经过B到C这样一个功能，同样你不用纠结于hanoi函数到底如何实现这个功能的，只要知道他有这么一个神奇的功能就行
最后：递归都有收尾的时候对吧，收尾就是当只有一块的时候汉诺塔怎么个玩法呢？很简单吧，直接把那一块有Amove到C我们就完成了，所以hanoni这个函数最后还要加上 if(n==1)move(one,three);（当只有一块时，直接有Amove到C位置就行）这么一个条件就能实现hanoin函数n>=1时......>>

问题十：递归和递推有什么不一样。用起来哪个快一些？？ 递推就是递推循环，递推或者说循环比递归更容易理解和运用，但递归算法在运行速度上更快，代码也比较简洁。递归算法也有缺点，主要是空间消耗比较大。从数学上说，所有的递归算法都可以用递推（循环）算法代替，但不是所有的循环算法都可以被递归代替。