递归：函数调用本身
递归与迭代的区别：
例子：fibonacci
递归：return fibonacci（n） = fibonacci（n-1） + fibonacci（n-2）； 递归：从高到底 从未知到已知 往回
迭代：for（i=2； i<=n； i++） 迭代：从低到高 从已知到未知 向上
fibonacci（i） = fibonacci（i-1） + fibonacci（i-2）；
（1）阶乘
（a）：递归方法
#include <stdio.h>
#include <ctype.h>
int stratum(int num);
main()
{
char c;
int n;
int result;
do
{
printf("input a number:/n");
scanf("%d", &n);
result = stratum(n);
printf("%d! = %d/n", n, result);
printf("continue? y or n/n");
getchar();
c = toupper(getchar()); //注意：这里要用两个getchar（）
}while(c == 'Y');
}
int stratum(int num)
{
if(num == 0 || num == 1)
return(1);
else
return(num*stratum(num-1));
}
（b）非递归方法：（即迭代）
/* no use recursive */
#include <stdio.h>
#include <ctype.h>
int stratum(int num);
main()
{
char c;
int n;
int result;
do
{
printf("input a number:/n");
scanf("%d", &n);
result = stratum(n);
printf("%d! = %d/n", n, result);
printf("continue? y or n/n");
getchar();
c = toupper(getchar());
}while(c == 'Y');
}
int stratum(int num)
{
int i;
int temp = 1;
if(num == 0 || num == 1)
return(1);
else
for(i = 2; i<=num; i++)
{
temp *= i;
}
return(temp);
}
====================================================
（2）fibonacci
（a）递归：
#include <stdio.h>
#include <ctype.h>
int fibonacci(int num);
main()
{
char c;
int n;
int result;
do
{
printf("input a number:/n");
scanf("%d", &n);
result = fibonacci(n);
printf("%d/n", result);
printf("continue? y or n/n");
getchar();
c = toupper(getchar());
}while(c == 'Y');
}
int fibonacci(int num)
{
if(num == 0 || num == 1)
return(1);
else
return(fibonacci(num-1) +fibonacci(num-2));
}
（b）非递归（迭代）
#include <stdio.h>
#include <ctype.h>
int fibonacci(int num);
main()
{
char c;
int n;
int result;
do
{
printf("input a number:/n");
scanf("%d", &n);
result = fibonacci(n);
printf("%d/n", result);
printf("continue? y or n/n");
getchar();
c = toupper(getchar());
}while(c == 'Y');
}
int fibonacci(int num)
{
int i;
int temp = 0;
int a = 1;
int b = 1;
if(num == 0 || num == 1)
return(1);
else
for(i = 2; i<=num; i++)
{
temp = a + b;
a = b;
b = temp;
}
return temp;
}
=====================================
（3）Hanoi塔 移动n个盘子 至少要2的n次方减1次
#include <stdio.h>
#include <ctype.h>
int hanoi(int num, char a, char b, char c);
main()
{
char c;
char A = 'A';
char B = 'B';
char C = 'C';
int i;
int n;
do
{
printf("input a number:/n");
scanf("%d", &n);
if(n == 0)
{
printf("no have disk/n");
}
else
hanoi(n, A, B, C);
printf("continue? y or n/n");
getchar();
c = toupper(getchar());
}while(c == 'Y');
}
int hanoi(int num, char a, char b, char c)
{
if(num == 1)
printf("%c -> %c/n", a, c);
else
{
hanoi(num-1, a, c, b);
printf("%c -> %c/n", a, c);
hanoi(num-1, b, a, c);
}
}