递归问题实际上是入栈出栈的一个过程,但有时候也会比较难理解,虽然用起来是比较方便的。
1 #include<iostream>
2 #include<string>
3 using namespace std;
4 #define SECONDS_PER_YEAR 365*24*3600
5 void move(int n, char a, char b)
6 {
7 cout<<n<<":" <<a<<"--->"<<b<<endl;
8
9 }
10
11 void hanio(int n, char a, char b, char c)
12 {
13 if(n==1)
14 move(1,a,c);
15 else
16 {
17 hanio(n-1,a,c,b);
18 move(n,a,c);
19 hanio(n-1,b,a,c);
20 }
21 }
22 int main()
23 {
24 int num;
25 cin>>num;
26 hanio(num,'A','B','C');
27 system("pause");
28 return 0;
29 }
解释一下上图,
n=3时,会把h(2,1,3,2),move(1,3),h(2,2,1,3)压入栈中
n=2时,会把h(2,1,3,2)弹出,压入h(1,1,2,3),move(1,2),h(1,3,1,2)压入栈中,依次这样。。。