递归算法还不是很理解!!高手教一教!

Question

逻辑性强..喜欢..理解到一半就晕了..喜欢也没用吖....

Answer 1

递归（recursion）是指把一个大的问题转化为同样形式但小一些的问题加以解决的方法。C语言允许一个函数调用它本身，这就是递归调用。即在调用一个函数的过程中又直接或间接地调用函数本身。不加控制的递归都是无终止的自身调用，程序中是绝对不应该出现这种情况的。为了防止无休止的递归，程序中应控制递归的次数，在某条件成立时进行递归，条件不成立不进行递归调用。并且在递归的调用过程中，不断改变递归的条件，以使递归条件不再成立。
同一问题可能既可以用递归算法解决，也可以用非递归算法解决，递归往往算法设计简单，出奇制胜，而普通算法（通常用循环解决）往往设计稍复杂。但执行效率递归算法逊于循环算法。递归反复调用自己，需要占用较多内存和计算机时间。但有一些问题只有用递归方法才能解决，如著名的汉诺塔问题。
递归程序设计的关键就是考虑问题的两种情况，一种是普遍情况即函数值等于把问题递推一步后的本函数的调用，一种是极端或端点情况，此时函数值有确定的一个值而无须再调用本函数。递归的过程就是从普遍情况逐步过渡到端点情况的过程。
例子：
5个坐在一起论年龄，问第五个人多少岁？他说比第四个人大两岁。问第四个人多少岁，他说比第三个人大两岁。问第三个人多少岁，他说比第二个人大两岁。问第二个人多少岁，他说比第一个人大两岁。问第一个人多少岁，他说10岁。请问第五个人几岁？
int age(int n)
{ int x;
if(n>1) x=age(n-1)+2;
else if(n==1) x=10;
return x;
}
void main( )
{ printf("%d",age(5));}

Answer 2

以著名的汉诺塔问题为例:
汉诺塔这是一个只有用递归方法才能够解决的问题。递归方法就是通过把问题不断转化为更简单的同样性质的问题而求得最终解决的方法。
从形式上，一个函数再调用它本身，这就是递归调用。即在调用一个函数的过程中又直接或间接地调用函数本身。无控制的递归都是无终止的自身调用，会导致死机。合理的递归程序设计应控制在某条件成立时进行递归，否则不再进行递归调用。通常在递归的调用过程中，不断改变递归的条件，以使递归条件到最后不再成立，这就能有结果。
递归程序设计的关键就是考虑问题的两种情况，一种是普遍情况即函数值等于把问题递推一步后的本函数的调用，一种是极端或端点情况，此时函数值有确定的一个值而无须再调用本函数。递归的过程就是从普遍情况逐步过渡到端点情况的过程。
就本题来说，若要将n个盘子从塔A移动到塔C，需用以下3个步骤：
（1）先设法把A上的n-1个盘子借助于C先移到B上；
（2）把A上的1个盘子（底部最大的盘子）移到C上；
（3）再设法把B上的n-1个盘子借助于A移到C上。
其中步骤（1）和（3）就是问题转化为更简单(n少了一个)的同样性质的(尽管起始位置和目标位置各异)递推一步后的问题。
这就是普遍情况。
它的极端或端点情况就是n=1即只有一个盘子时可以直接把盘子从A移到C上。
因此，如果函数hanoi(n,one,two,three)的功能是要把n个盘子从塔one移动到塔three，它的具体实现就是以下步骤：
if(n==1)
move(one,three);
else
{hanoi(n-1,one,three,two);
move(one,three);
hanoi(n-1,two,one,three);
}
由于本题是要打出移动的步骤，故move(one,three)就是打出one-->three形式即可，变量one,two,three中根据情况存放塔号（字符'A','B','C'），即执行printf("%c-->%c\n",one,three)。
还可以把hanoi函数中的两处move(one,three);直接换成两句printf("%c-->%c\n",one,three);并省去后边的move函数，这样程序更精炼。即程序为：
#include <stdio.h>
hanoi(n,one,two,three)
{
if(n==1)
printf("%c-->%c\n",one,three);
else
{hanoi(n-1,one,three,two);
printf("%c-->%c\n",one,three);
hanoi(n-1,two,one,three);
}
}
void main()
{
int m;
printf("Input the number of diskes:");
scanf("%d",&m);
printf("The step to moveing %d diskes:\n",m);
hanoi(m,'A','B','C');
}
/*
运行结果:
Input the number of diskes:3
The step to moveing 3 diskes:
A-->C
A-->B
C-->B
A-->C
B-->A
B-->C
A-->C
*/