c语言递归函数

　　递归函数：

　　编程语言中，函数Func(Type a,……)直接或间接调用函数本身，则该函数称为递归函数。递归函数不能定义为内联函数。

　　在数学上，关于递归函数的定义如下：对于某一函数f(x)，其定义域是集合A，那么若对于A集合中的某一个值X0，其函数值f(x0)由f(f(x0))决定，那么就称f(x)为递归函数。

　　函数介绍：

　　在数理逻辑和计算机科学中，递归函数或μ-递归函数是一类从自然数到自然数的函数，它是在某种直觉意义上是"可计算的" 。事实上，在可计算性理论中证明了递归函数精确的是图灵机的可计算函数。递归函数有关于原始递归函数，并且它们的归纳定义(见下)建造在原始递归函数之上。但是，不是所有递归函数都是原始递归函数 — 最著名的这种函数是阿克曼函数。

　　其他等价的函数类是λ-递归函数和马尔可夫算法可计算的函数。

　　例子：

　　//代码1

　　void func()

　　{

　　//

　　if()

　　func();

　　else

　　//

　　}

　　条件：

　　一个含直接或间接调用本函数语句的函数被称之为递归函数，在上面的例子中能够看出，它必须满足以下两个条件：

　　1） 在每一次调用自己时，必须是（在某种意义上）更接近于解；

　　2） 必须有一个终止处理或计算的准则。

　　梵塔的递归函数：

　　//C

　　void hanoi(int n,char x,char y,char z)

　　{

　　if(n==1)

　　move(x,1,z);

　　else

　　{

　　hanoi(n-1,x,z,y);

　　move(x,n,z);

　　hanoi(n-1,y,x,z);

　　}

　　}

我觉得这样可能比较好理解一点

有三根柱子，标记为A, B, C

先要理解函数hanoi(n,A,B,C) 的意思是借助于B柱子将A上面的n个盘子移到C上面，必须充分对应到各个参数。

如果想将n个盘子从A柱子移动到C柱子

可以分为这样几个步骤

（1）必须将A最下面也就是最大的那个盘子移动到C最下面

首先需要借助C柱子将A上面的n-1个盘子移动到B上面

就是hanoi(n-1,A,C,B) 。

此时A上面只有一个最大的盘子，B上面按序放着n-1个盘子，C上面有0个盘子。

（2）将A上面的盘子移动到C上面，只需要1步。

此时A上面有0个盘子，B上面按序放着n-1个盘子，C上面只有一个最大的盘子。

（3）最后借助于A柱子将B上面n-1个盘子移到C上面即可

就是hanoi(n-1,B,A,C) 。

所以实际上数学推导公式为f(n)=2f(n-1)+1，其中f(1)=1，f(n)表示将n个盘子从A柱子移到C柱子的步数

如果还不明白的欢迎hi我 啊

汉诺塔问题（又称河内塔问题）是根据一个传说形成的一个问题：

有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：

1 每次只能移动一个圆盘；

2 大盘不能叠在小盘上面。

提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须尊循上述两条规则。

问：如何移？最少要移动多少次？

一般取N=64。这样，最少需移动264-1次。即如果一秒钟能移动一块圆盘，仍将需584554亿年。目前按照宇宙大爆炸理论的推测，宇宙的年龄仅为137亿年。

在真实玩具中，一般N=8；这将需移动255次。如果N=10，需移动1023次。如果N=15，需移动32767次；这就是说，如果一个人从3岁到99岁，每天移动一块圆盘，他仅能移动15块。如果N=20，需移动1048575次，即超过了一百万次。

先看hanoi(1, one, two, three)的情况。这时直接将one柱上的一个盘子搬到three柱上。注意，这里one柱或three柱到底是A、B还是C并不重要，要记住的是函数第二个参数代表的柱上的一个盘被搬到第四个参数代表的柱上。为方便，将这个动作记为：

one =》three

再看hanoi(2, one, two, three)的情况。考虑到hanoi(1)的情况已经分析过了，可知这时实际上将产生三个动作，分别是：

one =》two

one =》three

two =》three

很显然，这实际上相当于将one柱上的两个盘直接搬到three柱上。

再看hanoi(3, one, two, three)的情况。分析

hanoi(2, one , three, two)

one =》three

hanoi(2, two, one, three)

即：先将one柱上的两个盘搬到two柱上，再将one柱上的一个盘搬到three柱上，最后再将two柱上的两个盘搬到three柱上。这不就等于将one柱上的三个盘直接搬到three柱上吗？

运用归纳法可知，对任意n，

hanoi(n-1, one , three, two)

one =》three

hanoi(n-1, two, one, three)

就是先将one柱上的n-1个盘搬到two柱上，再将one柱上的一个盘搬到three柱上，最后再将two柱上的n-1个盘搬到three柱上。这就是我们所需要的结果！

回答者：wuchenghua121 - 经理 四级 12-5 11:51

汉诺塔

汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。解答结果请自己运行计算，程序见尾部。面对庞大的数字(移动圆片的次数)18446744073709551615，看来，众僧们耗尽毕生精力也不可能完成金片的移动。

后来，这个传说就演变为汉诺塔游戏:

1有三根杆子A,B,C。A杆上有若干碟子

2每次移动一块碟子,小的只能叠在大的上面

3把所有碟子从A杆全部移到C杆上

经过研究发现，汉诺塔的破解很简单，就是按照移动规则向一个方向移动金片：

如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C

此外，汉诺塔问题也是程序设计中的经典递归问题。

补充：汉诺塔的算法实现（c++）

#include <fstream>

#include <iostream>

using namespace std;

ofstream fout("outtxt");

void Move(int n,char x,char y)

{

fout<<"把"<<n<<"号从"<<x<<"挪动到"<<y<<endl;

}

void Hannoi(int n,char a,char b,char c)

{

if(n==1)

Move(1,a,c);

else

{

Hannoi(n-1,a,c,b);

Move(n,a,c);

Hannoi(n-1,b,a,c);

}

}

int main()

{

fout<<"以下是7层汉诺塔的解法:"<<endl;

Hannoi(7,'a','b','c');

foutclose();

cout<<"输出完毕！"<<endl;

return 0;

}

C语言精简算法

/ Copyrighter by SS7E /

#include<stdioh> / Copyrighter by SS7E /

void hanoi(int n,char A,char B,char C) / Copyrighter by SS7E /

{

if(n==1)

{

printf("Move disk %d from %c to %c\n",n,A,C);

}

else

{

hanoi(n-1,A,C,B); / Copyrighter by SS7E /

printf("Move disk %d from %c to %c\n",n,A,C);

hanoi(n-1,B,A,C); / Copyrighter by SS7E /

}

}

main() / Copyrighter by SS7E /

{

int n;

printf("请输入数字n以解决n阶汉诺塔问题：\n");

scanf("%d",&n);

hanoi(n,'A','B','C');

}/ Copyrighter by SS7E /

回答者： Vanquisher_ - 举人 五级 12-5 13:57

parcel::::::::::

program hanoi;

functionhanoi(x:integer):longint;

begin

if x=1 then hanoi:=1;

if x=2 then hanoi:=3;

else

begin

hanoi:=2hanoi(x-1)+1;

end;

end;

begin

read(x){第几个数 }

write(hanoi(x));

end

思想就是：第N个就等于第n-1个乘以2+1次