递归算法讲解

1. 求汉诺塔递归全过程的算法详解图，记得一定要是图释哦！！！

图解是什么意思呀。
这个算法 那么简单没必要搞得那么复杂吧。
an = an-1 + 1;
你明白这个等式的意义吗？
这个等式已经包含了递归算法的全部含义。

an 表示 n个数的和，an-1 表示n-1个数的和 ，an = an-1 + 1;表示n个数的和可以通过n-1个数的和来求的。
上述说明哪些情况可以使用递归呢？
那就是：已知前一个步骤可以求得后一个步骤的结果的情况，并且前一个步骤和后一个步骤是有规律过度的。
比如汉诺塔问题：
移n个盘是已移n-1个盘为条件的，两者的共同点是移盘。所以可以用f（n）表示移n个盘，f(n-1)表示移n-1个盘，那么移n个盘和移n-1个盘有什么关系呢？
这就需要预先分析问题才能得出具体的关系
在这个问题中，把n个盘从a移到c需要三个步骤来完成。
1.n-1个盘从a移到b
2 1个盘从a移到c
3 n-1个盘从b移到c
已知n-1个盘从a移到b是可行的，为什么？
因为移1个盘是可行，那么移2个盘也是可行，移 3个盘是已移2个盘为条件的，所以移3个盘也是可行的，所以移n个 盘是可行的。
所以根据已知条件可以解得：
设f(n, a, b,c) 表示 把n个盘从a移到c 借助b --------------------------这里很关键，这是搞懂递归的关键关键。
那么把n-1个盘从a移到b 借助c 怎样表示呢？
很明显是：f(n-1, a, c,b)
那么把1个盘从a移到c怎样表示呢?
很明显是：f(1, a, b,c)
那么把n-1个盘从b移到c 借助a 怎样表示呢？
很明显是：f(n-1, b, a,c)

所以f(n, a, b,c) = ( f(n-1, a,c,b) , f(1, a, b,c), f(n-1, b,a,c))
这和等差等比数列一个原理。
没有什么 特别的。

记住是问题有这样递推关系才可以使用这种方法。
如果要你计算1+2+8+22 的结果 你就不能使用递归。
因为该问题的后一步骤与前一步骤不具有规律性，所以已知前一个步骤并不能求的后一个步骤的值
1+2+3+4 ...+
这个问题就可以使用递归
原因你懂了吧。
至于爬楼梯问题，无限级分类 问题等一些递归问题，那不过时小菜一碟。
一句话：后一步骤依赖前一步骤并且二者联系具有规律性，运用递归必然成功。

2. 汉诺塔 递归算法的详细解释请教高手

为了实现 n个盘从 借助c 从a 移动到 b
思路如下：
首先考虑极限当只有一个盘的时候 只要 盘直接从 a -> b即可
那么当有2个盘的时候就只要先把1号盘从a -> c 然后 把2号盘 a->b 再 把 2好盘从 c - > b
那么当有n个盘的时候你只要先把 n-1个 盘 借助 b 移动到 c 然后将 n号盘从 a -> b
那么这时候只要将 n-1想办法从c移动到 b 借助 a 那么就可以先把 n-2个盘借助b移动到a
然后 把n-1号盘从c-> b如此递归就是了！
#include <stdio.h>

void mov(int n,char a,char b)
{
printf("盘%d : 从 %c ---> %c\n",n,a,b);
}

void Hanoi(int n,char a,char b,char c)
{
if(n == 0) return ;
Hanoi(n-1,a,c,b);
mov(n,a,b);
Hanoi(n-1,c,b,a);

}
int main()
{
Hanoi(2,'a','b','c');
return 0;
}

3. 递归是什么要详细解释

阶乘, 斐波那契数列, 快速排序, 还有汉诺塔问题, 都是递归的比较经典的问题, 你要什么例子呢? 你究竟是想学递归还是做什么? 楼上几位讲得是不错的, 唯一遗憾的是都不是用PASCAL语言编的.
下面试一下用PASCAL编一个汉诺塔的程序, 我手头没有书, 想到哪编到哪, 不一定太规范.
有A, B, C三个柱, 在A上N个盘子, 要移到C上去.
用中文建一个程序就是:
begin
移(N-1)个盘子(A到B, 以C为中介); {顶上的盘子}
移1个盘子(A到C); {最底的盘子}
移(N-1)个盘子(B到C, 以A为中介); {第一步移到B的盘子}
end.

对于移一个盘子, 我们只要简单地打印一下就可:
procere MoveSingle(Origin, Dest: Char);
begin
Writeln(Origin, '==>', Dest);
end;

这一段不编子程序也可.

对于移动多个盘子, 按前面分析的, 可如此实现:
procere MoveMult(Origin, Dest, Medi: Char, n: Integer);
begin
MoveMult(Origin, Medi, Dest, n-1); {将顶上的盘子移走}
MoveSingle(Origin, Dest); {移最下的盘子}
MoveMult(Medi, Dest, Origin, n-1); {再移顶上的盘子}
end;

注意, 在MoveMult子程序中又调用了MoveMult自身, 这就是所谓的递归.

分析一下, 当有3个盘子时, 为: 先移2个(A==>B), 再移底部的(A==>C), 再把B上的2个移至C.
那么移2个是如何实现的呢? 先移1个(Ori==>Med), 再移1个(Ori==>Dest), 再移一个(Med==>Dest).
移1个时算法如何? 显然又要调用移0个, 而移0个则调用移-1个, 这显然有问题了. 程序一直会进行下去, 直到堆栈溢出为止, 程序死了.
解决的办法是: 当个数为1时直接调用MoveSingle不再递归.
所以递归要有一个终止条件, 否则会无限进行下去. 修改后的递归算法为:

procere MoveMult(Origin, Dest, Medi: Char, n: Integer);
begin
if n > 1 then {当盘子数大于1时递归}
begin
MoveMult(Origin, Medi, Dest, n-1); {将顶上的盘子移走}
MoveSingle(Origin, Dest); {移最下的盘子}
MoveMult(Medi, Dest, Origin, n-1); {再移顶上的盘子}
end else MoveSingle(Origin, Dest); {当盘子数不大于1时直接移动}
end;

无限递归是递归算法中要注意的, 如果你设计多了, 自然知道什么时候可能会出现无限递归.

完整程序为:
program Hanoi(input, output);
var
n: Integer;

procere MoveSingle(Origin, Dest: Char);
begin
Writeln(Origin, '==>', Dest);
end;

procere MoveMult(Origin, Dest, Medi: Char, n: Integer);
begin
if n > 1 then
begin
MoveMult(Origin, Medi, Dest, n-1);
MoveSingle(Origin, Dest);
MoveMult(Medi, Dest, Origin, n-1);
end else MoveSingle(Origin, Dest);
end;

begin
Writeln('Hanoi program');
Write('Input a number: ');
Readln(n);
MoveMult('A', 'C', 'B', n);
end.

没经调试, 如果你要用的话, 自己测试一下.

4. 递归的通俗解释是什么

程序调用自身的编程技巧称为递归（ recursion）。递归作为一种算法在程序设计语言中广泛应用。

一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

递归的缺点：

递归算法解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。

以上内容参考：网络-递归

5. 什么是递归算法有什么作用

作者名：不详 来源：网友提供 05年7月7日

无法贴图 ，自己到 http://51zk.csai.cn/sjjg/NO00223.htm 看去吧

1、调用子程序的含义：
在过程和函数的学习中，我们知道调用子程序的一般形式是：主程序调用子程序A，子程序A调用子程序B，如图如示，这个过程实际上是：

＠当主程序执行到调用子程序A语句时，系统保存一些必要的现场数据，然后执行类似于BASIC语言的GOTO语句，跳转到子程序A（为了说得简单些，我这里忽略了参数传递这个过程）。
＠当子程序A执行到调用子程序B语句时，系统作法如上，跳转到子程序B。
＠子程序B执行完所有语句后，跳转回子程序A调用子程序B语句的下一条语句（我这又忽略了返回值处理）
＠子程序A执行完后，跳转回主程序调用子程序A语句的下一条语句
＠主程序执行到结束。
做个比较：我在吃饭（执行主程序）吃到一半时，某人叫我（执行子程序A），话正说到一半，电话又响了起来（执行子程序B），我只要先接完电话，再和某人把话说完，最后把饭吃完（我这饭吃得也够累的了J）。
2、认识递归函数
我们在高中时都学过数学归纳法，例：
求 n！
我们可以把n！这么定义

也就是说要求3！，我们必须先求出2！，要求2！，必须先求1！，要求1！，就必须先求0！，而0!=1，所以1!=0!*1=1，再进而求2!，3!。分别用函数表示，则如图：

我们可以观察到，除计算0！子程序外，其他的子程序基本相似，我们可以设计这么一个子程序：
int factorial(int i){
int res;
res=factorial(I-1)*i;
return res;
}
那么当执行主程序语句s=factorial(3)时，就会执行factorial(3),但在执行factorial(3)，又会调用factorial(2)，这时大家要注意，factorial(3)和factorial(2)虽然是同一个代码段，但在内存中它的数据区是两份！而执行factorial(2)时又会调用factorial（1），执行factorial（1）时又会调用factorial（0），每调用一次factorial函数，它就会在内存中新增一个数据区，那么这些复制了多份的函数大家可以把它看成是多个不同名的函数来理解；
但我们这个函数有点问题，在执行factorial（0）时，它又会调用factorial（－1）。。。造成死循环，也就是说，在factorial函数中，我们要在适当的时候保证不再调用该函数，也就是不执行res=factorial(I-1)*i;这条调用语句。所以函数要改成：
int factorial(int i){
int res;
if (I>0) res=factorial(I-1)*i; else res=1;
return res;
}
那么求3!的实际执行过程如图所示：

3、如何考虑用递归的方法来解决问题
例：求s=1+2+3+4+5+6+……+n
本来这个问题我们过去常用循环累加的方法。而这里如要用递归的方法，必须考虑两点：
1） 能否把问题转化成递归形式的描述；
2） 是否有递归结束的边界条件。
设:函数s(n)=1+2+3+…+(n-1)+n
显然递归的两个条件都有了：
1） s(n) =s(n-1)+n
2） s(1)=1
所以源程序为：
int progression(int n){
int res;
if (n=1 )res=1 else res=progression(n-1)+n;
return res;
}
4、递归的应用
中序遍历二叉树
void inorder (BinTree T){
if (T){
inorder(T->lchild);
printf(“%c”,T->data);
inorder(T->rchild);
}
}
现假设树如图（为了讲解方便，树很简单）

＠执行第一次调用inorder1，T指向顶结点，T不为空，所以第二次调用inorder2；
＠T指向顶结点的左子树结点也就是B，不为空，所以第三次调用inorder3；
＠T指向B结点的左子树结点，为空，所以什么都不执行，返回inorder2；
＠打印B结点的DATA域值“b”；
＠第四次调用inorder4，去访问B子树的右结点
＠T指向B结点的右子树结点，为空，所以什么都不执行，返回inorder2；
＠返回inorder1；
＠打印A结点的DATA域值“a”；
＠第五次调用inorder5，去访问A子树的右结点；
＠T指向A结点的右子树结点，为空，所以什么都不执行，返回inorder1；
＠inorder1执行完毕，返回。

6. 关于递归算法的题，哪位大侠给我解释下………………

第一次调用方法先开始执行输出n+A，等待递归调用完成以后，再输出n+B，最后方法运行完毕。
在这里可以发现在递归调用的时候，没有改变它自己的n值。所以在递归调用之前的n和调用递归之后的n值是相同的。如果你了解栈的话就很好理解了，先进后出。这了也就是输出A越早的，输出B就越晚。

7. 汉诺塔递归算法求详解 （研究了5天了，没有理解，如果能教会我愿支付宝付现金20元）

首先要知道汉诺塔的基本思路.
汉诺塔有3根柱子. 为什么要有3根呢? 那是因为要直接使一个柱子上的盘片全部移动到另一根柱子是不行的,必须要通过第三根柱子来中转一下.
这种中转思路就是关键了.
具体来说,如果我们要把A柱子上的盘片移动到C柱子上,那么首先我们可以通过"某种方式"将A柱子上除了最底下的盘片以外的所有盘片移动到B柱子上去,也就是拿B柱子当中转. 然后下一步就可以直接把A柱子上最底层的那张盘片移动到C柱子上了. 最后,我们再以同样的方式,将B柱子上剩下的那堆盘片以同样的"某种方式"移动到C上. 总体来看,我们就完成了A->C的盘片移动操作.

那么剩下的问题就是,这"某种方式"是什么呢? 其实思考一下可以发现,在进行这"某种方式"的时候,除去A上最大的那个,其余盘片都是我们需要操作的, 这个时候由于A是最大,其他的盘片对他来说移动都没有限制的(都会比他小). 那么我们就可以暂时忽视这个最大的盘片.

以上面的例子来说,我们要移动A柱子上除了底层之外的所有盘片到B柱上,就可以暂时忽略掉A上最大的那个盘片. 发现没有, 这个时候我们的问题变成是: 将A上的所有盘片(因为已经忽视掉了最大的那个了)移动到B上,C可以作为转接(因为上面没有盘片).

这一步意味着我们把一个n个盘片的汉诺塔问题转化成了n-1个盘片的汉诺塔问题,从而这里面就包含了递归意义.

最后说回到你的程序. 函数hanoi(n,a,b,c)正是这样一个意味: 打印将a柱子上的n个盘片以b为中转移动到c上的操作步骤. 而可以看到,在执行这个函数的时候,如果n=1,那么由于只有一个盘片,可以直接打印a->c, 如果n>1,则先用hanoi(n-1,a,c,b), 以c为中转将a上的n-1个盘片先移动到b上,再打印a->c,即将a上剩下最大的那个盘片移动到c, 然后再调用hanoi(n-1,b,a,c), 以a为中转将b上的盘片移动到c上.
按如此的递归逻辑下去就可以得到全部的操作过程了.

8. 全排列递归算法

希望我的答复可以帮助你加深理解：

第一，perm函数中的条件for(int i=k;i<=m;i++)应更正为 for(int i=k;i<m;i++)

第二，你可以在核心步骤的前后打印有关变量的值，分析查看每一步的具体执行情况，这是编程调试的重要能力，要加强。
第三，以下是我提供的附件程序及运行结果（以1,2,3这个数组的全排列），可辅助分析：

1. 程序源码=================================================
#include <stdio.h>
#include <stdlib.h>
int N,P=0;

void swap(int a[],int i,int j)
{
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}

void perm(int a[],int k,int m,int pk,int pm)
{
int i;
/*k为中间变量，m初始化为参与排列元素的起始坐标和终止坐标
pk,pm分别表示参与排列元素的起始坐标和终止坐标，整个递归过程保持不变*/
if(k==m)
{
printf("----->perm %d :\n",P/N+1);/*打印提示*/
for(i=pk;i<pm;i++)
{
printf("%d ",a[i]);
P=P+1;
}
printf("\n\n");
}
else
{
for(i=k;i<m;i++)
{
printf("a %d,%d,%d,%d,%d\n",i,k,a[0],a[1],a[2]);
swap(a,k,i);
printf("b %d,%d,%d,%d,%d\n",i,k,a[0],a[1],a[2]);
perm(a,k+1,m,pk,pm);
printf("c %d,%d,%d,%d,%d\n",i,k,a[0],a[1],a[2]);
swap(a,k,i);
printf("d %d,%d,%d,%d,%d\n",i,k,a[0],a[1],a[2]);
}
}
}

int main()
{
/*调节以下N值及对应数组内容，可打印对应数组对应的全排列*/
N=3;
int t[]={1,2,3};
/*调节以上N值及对应数组内容，可打印对应数组对应的全排列*/

perm(t,0,N,0,N);
printf("----->Over!\n");/*打印提示*/
system("pause");
return 0;
}

2.打印结果 ============================================================

a 0,0,1,2,3
b 0,0,1,2,3
a 1,1,1,2,3
b 1,1,1,2,3
a 2,2,1,2,3
b 2,2,1,2,3
----->perm 1 :
1 2 3

c 2,2,1,2,3
d 2,2,1,2,3
c 1,1,1,2,3
d 1,1,1,2,3
a 2,1,1,2,3
b 2,1,1,3,2
a 2,2,1,3,2
b 2,2,1,3,2
----->perm 2 :
1 3 2

c 2,2,1,3,2
d 2,2,1,3,2
c 2,1,1,3,2
d 2,1,1,2,3
c 0,0,1,2,3
d 0,0,1,2,3
a 1,0,1,2,3
b 1,0,2,1,3
a 1,1,2,1,3
b 1,1,2,1,3
a 2,2,2,1,3
b 2,2,2,1,3
----->perm 3 :
2 1 3

c 2,2,2,1,3
d 2,2,2,1,3
c 1,1,2,1,3
d 1,1,2,1,3
a 2,1,2,1,3
b 2,1,2,3,1
a 2,2,2,3,1
b 2,2,2,3,1
----->perm 4 :
2 3 1

c 2,2,2,3,1
d 2,2,2,3,1
c 2,1,2,3,1
d 2,1,2,1,3
c 1,0,2,1,3
d 1,0,1,2,3
a 2,0,1,2,3
b 2,0,3,2,1
a 1,1,3,2,1
b 1,1,3,2,1
a 2,2,3,2,1
b 2,2,3,2,1
----->perm 5 :
3 2 1

c 2,2,3,2,1
d 2,2,3,2,1
c 1,1,3,2,1
d 1,1,3,2,1
a 2,1,3,2,1
b 2,1,3,1,2
a 2,2,3,1,2
b 2,2,3,1,2
----->perm 6 :
3 1 2

c 2,2,3,1,2
d 2,2,3,1,2
c 2,1,3,1,2
d 2,1,3,2,1
c 2,0,3,2,1
d 2,0,1,2,3
----->Over!
请按任意键继续. . .

9. 汉诺塔分治递归算法解释！

hanoi中的参数：从A（源）通过B（中转）移动到C（目的）
先把n-1个从A通过C移动到B：hanoi(n-1,A,C,B,time);
再把最后那个从A移到C：move(A,C);
然后把那n-1个从B通过A移到C：hanoi(n-1,B,A,C,time)
注意每一步的目的是什么

10. 图的广度优先遍历的递归算法（附详细解释）

广度优先遍历不是用队列的吗、、、、深度优先遍历才是用递归回溯啊