Question

汉塔函数递归的调用是如何进行的，n=3时结果是如何让出来的，求大神分析结果

# include <stdio.h>
int main ()
{
void hanoi(int n , char one , char two , char three);
hanoi(3,'A' , 'B' , 'C');
}
void hanoi(int n , char one , char two , char three)
{
void move (char x , char y);
if(n == 1)
{
move( one , three);
}
else
{
hanoi(n - 1 , one , three , two); //函数递归调用
move( one , three);
hanoi(n - 1 , two , one , three);
}
}

void move( char x , char y)
{

printf("%c ——> %c \n" , x , y);

}

Answer 1

递归本质是整体法，先给你讲个例子让你知道什么是整体法，
题目，1到10排列是怎样的？
答案：1,2，3,10
换一种解法
设1，2，，，5 排列称为f(n<=5)
6,7,,,10排列称为f(10>=n>5)
所以1到10的排法是由
f(n<=5)和f(10>=n>5)组成的，
已知f(n<=5)为1，2，，，5
f(10>=n>5)为6,7,,,10，
所以最终结果为12,，，10。
所以1,2,,,10的排列也可以用f(n<=5)和f(10>=n>5)表示。
好了，讲完了整体法，
前面说过，递归算法本质也是整体法，
n项递归是依赖n-1项的，所以可以把n-1项看成整体，
举个例子，
hanio(3,'a','b','c')由哪些整体构成呢？
从程序可以看出是由：
hanoi(2 , ‘a’ , 'c' , 'b');//整体1
move('a','c');//整体2
hanoi(2, 'b','a','c'); //整体3
因此只要求出hanoi(2 , ‘a’ , 'c' , 'b');和hanoi(2, 'b','a','c');

就行了，
那么hanoi(2 , ‘a’ , 'c' , 'b')由哪些整体组成呢？
从程序可以看出是由：
hanoi(1 , ‘a’ , 'b' , 'c');
move('a','b');
hanoi(1 , ‘c’ , 'a' , 'b');
所以hanoi(2 , ‘a’ , 'c' , 'b')的结果是：
move(a,c);
move(a,b);
move(c,b);
同理分析hanoi(2, 'b','a','c')的组成部分：
hanoi(1 , ‘b’ , 'c' , 'a');
move('b','c');
hanoi(1 , ‘a’ , 'b' , 'c');
也就是：
move(b,a)
move(b,c)
move(a,c)
最后看回hanio(3,a,b,c)的组成部分：
hanoi(2 , ‘a’ , 'c' , 'b');
move('a','c');
hanoi(2, 'b','a','c');
那么可以将hanoi(2 , ‘a’ , 'c' , 'b')的结果替代hanoi(2 , ‘a’ , 'c' , 'b')这一句，hanoi(2, 'b','a','c')同样需要替代
结果就是：
move(a,c);
move(a,b);
move(c,b);
//上面是hanoi(2 , ‘a’ , 'c' , 'b')的结果
move('a','c');
//下面是hanoi(2, 'b','a','c')的结果
move(b,a)
move(b,c)
move(a,c)
解答完毕。