汉洛塔递归实现的思考（C语言）

汉洛塔是古印度神话产生的智力玩具，他的玩法是，有三个柱子分别为A,B,C，A柱上面有n个盘子上面小下面大堆叠放在一起，现在要求激将A柱上的盘子全部移到C柱上面，并且一次只能移动一个盘子，必须是小盘在大盘的上面。现在要求用C语言递归来完成，并统计递归调用的次数。

这个实现是递归的强大功能的体现，废话不多说，请看源码：

#include<stdio.h>
void move(int n,int *cnt,char A,char B,char C)
{ if(n==1) { printf("%d号盘：%c-->%c\n",n,A,C); //如果还剩一个盘或者只有一个盘时，直接将1号盘移到C柱 (*cnt)++; //递归调用次数加1 } else { move(n-1,cnt,A,C,B); //将n-1个盘从A柱上借助于C柱移到B柱上 printf("%d号盘：%c-->%c\n",n ,A,C); //当将n-1个盘移到B柱成功时直接将A柱上的盘移到C柱 move(n-1,cnt,B,A,C); //再次将n-1个盘从B柱上借助于A柱移到C柱上 (*cnt)++; //递归调用次数加1 }

}
int main(void)
{ int h; int cnt = 0; printf("\ninput number:\n"); scanf("%d",&h); printf("the step to moving %2d diskes:\n",h); move(h,&cnt,'A','B','C'); printf("一共执行了%d次！\n",cnt);
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
 

我这里给出的源码是极为精简的，但是很健壮！现在分析如下：

首先，梳理一下思路，要用递归实现的前提是，问题规模更大的解决依赖于问题规模更小的解决，也就是说要想移动n个盘子，必须先移动n-1个盘子，这时递归的基础。那么现在有三个柱子，该如何移动呢？比较好的解决方案是：可以将n-1个盘子以C柱为中转站移动到B柱上，这样A柱上最下面的那个盘子就可自由地移动到C柱上了，然后在将n-1个盘子以A柱为中转站移动到C柱上，这就是上面代码核心的解决算法。

看到这里，很多人又有疑问，感觉这个解决方案，似乎理解了又似乎没理解，这时怎么回事？其实这就是递归的理解问题。在这个问题中，n个盘子会始终按照这个算法执行，当执行到n==1的时候一下子就返回，层层回叠返回最终的结果。

这个里面还有一个有意思的问题，就是递归调用的参数是个变量，比如说

move(n-1,cnt,A,C,B);

这一步中，他将C给了B，B给了C，这是个互换，又因为当n==1的时候不会再递归调用，故当盘子数为奇数时两个数会互换，而是偶数时就不会互换，举个例子如下：

#include <iostream>
using namespace std;
void swap (int n,int a,int b)
{ if (n == 1) { cout << "a="<< a << "\tb=" << b << endl; return; } else { swap(n-1,b,a); }
}
int main (void)
{ int a = 1; int b = 2; swap(3,a,b);
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
 

在这个例子中，当main函数中个传参的第一参数是奇数时a，b就不会互换，偶数时就会互换，这也是个互换数字的算法呢！

例外附注一下，汉洛塔的递归调用的个数是2的n次方减1，故大家在试的时候，不要输入太大的n值，以免在DOS下看不全结果！！

文章来源: chenhx.blog.csdn.net，作者：谙忆，版权归原作者所有，如需转载，请联系作者。

原文链接：chenhx.blog.csdn.net/article/details/50346523