1、根据阶乘定义公式，写出该函数递归算法。
#include<stdio.h>
void main(void)
{
int result = Fact(-1);
printf("%d\n", result);
}
int Fact(int n)
{
if(n < 0)
{
printf("输入数字必须大于等于零\n");
return -1;
}
else if(n == 0) return 1; //递归出口
else
{
return n * Fact(n-1);
}
}
2、汉诺塔：每次只能移动一块儿，将全部碟子从A柱移到C柱，而且从头到尾不能出现大碟盖在小碟上。
n为1时，直接从A -> C（一步）；
n大于1时：
1、n-1个从A->B（递归处理）；
2、第n个从A->C（一步）；
3、n-1个从B->C（递归处理）。
#include<stdio.h>
void Hanoi(int,char,char,char);
void Move(char,char);
void main()
{
Hanoi(4, 'A', 'B', 'C');
}
//递归方法
void Hanoi(int n, char a, char b, char c)
{
if(n == 1) //递归出口
{
Move(a, c);
}
else if(n > 1)
{
Hanoi(n-1, a, c, b);
Move(a, c);
Hanoi(n-1, b, a, c);
}
else
{
printf("输入有误");
}
}
//移动方法
int n = 0;
void Move(char c1, char c2)
{
n++;
printf("第%d步从%c移到%c\n", n, c1, c2);
}
3、斐波纳挈数列（递归与循环效率比较）：没有0项，从1开始，1、2项值都为1，后面项值都是前两项值的和。
//递归写法
int Fabonaci(int n)
{
if(n == 1||n == 2)
{
return 1;
}
else if(n > 2)
{
return Fabonaci(n-1)+Fabonaci(n-2);
}
else
{
printf("输入有误");
return -1;
}
}
//循环写法
int Fabonaci2(int n)
{
if(n == 1 || n == 2)
{
return 1;
}
else if(n > 1)
{
int i, num1 = 1, num2 = 1, result = 0;
for(i=3; i<=n; i++)
{
result = num1 + num2;
num1 = num2;
num2 = result;
}
return result;
}
else
{
printf("输入有误");
return -1;
}
}
而利用循环求解的时间复杂度则为O(n)。
总结：
1、递归就是方法自己调用自己；
2、利用递归写程序记得写出口，不然会死循环；
3、递归不一定就好于循环，反之亦然。
