爱华网本文介绍Fibonacci数列用递归法和迭代法区别，重点在于本文把递归法进行了优化，用二叉树，三叉树，尾归法分别来设计递归算法并和迭代法进行比较，而且这个代码把这些功能做了模块化，方便使用。（c语言，vs2013编译器）（文章后会附代码）
二叉树递归算法函数名Fib_rec1.
三叉树递归算法函数名Fib_rec2.
尾归法递归算法函数名Fib_rec3.
递迭代法算法函数名Fib_ite.
Fibonacci数列递归法和迭代法的模块化测试――工具/原料vs或者vc++Fibonacci数列递归法和迭代法的模块化测试――方法/步骤
Fibonacci数列递归法和迭代法的模块化测试 1、
程序主界面，
模块一为二叉树递归算法和迭代法比较
模块二为三叉树递归算法和迭代法比较
模块三为尾归法递归算法和迭代法比较
数字4退出
Fibonacci数列递归法和迭代法的模块化测试 2、
主界面错误输入测试
Fibonacci数列递归法和迭代法的模块化测试 3、
次级模块界面，输入fiboncci位数开始测试
Fibonacci数列递归法和迭代法的模块化测试 4、
定义了越界值，非法输入时报错
Fibonacci数列递归法和迭代法的模块化测试_递归法
Fibonacci数列递归法和迭代法的模块化测试 5、
程序可在次级界面选择继续输入数字测试，或者返回主界面，或者退出
Fibonacci数列递归法和迭代法的模块化测试 6、
代码如下
#include<stdio.h> //预处理头文件
#include<time.h>
#include<stdlib.h>
//函数声明，后面介绍函数功能
void InitMenu();
void Select();
void SubSelect(char a);
long Fib_ite(int n);
long Fib_rec1(int n);
long Fib_rec2(int n);
long Fib_rec3(int a, int b, int n);
void Fib1();
void Fib2();
void Fib3();
int Transfrom(char a[]);
//主函数
int main()
{
InitMenu();
return 0;
}
//初始化主界面函数
void InitMenu()
{
printf("**************************************************************n");
printf("** 欢迎进入Fibonacci测试系统主界面，你可以做以下事情: **n");
printf("** 1 选择此选项可以进行对Fibonacci中递归算法优化一进行选择 **n");
printf("** 2 选择此选项可以进行对Fibonacci中递归算法优化二进行选择 **n");
printf("** 3 选择此选项可以进行对Fibonacci中递归算法优化三进行选择 **n");
printf("** 4 选择此选项可以退出 **n");
printf("**************************************************************n");
Select();
}
//主界面选择函数
void Select()
{
int n;
scanf_s("%d", &n); //数字录入
if (n<1 || n>4) //判断字符正确性
{
fflush(stdin); //对输入字母时产生的buffer越界进行清理，在输入错误时进行
printf("不可以输入其他字符，请继续选择！！！n"); //输出错误信息
InitMenu(); //输入错误时，继续返回初始化函数输入
}
switch (n) //对录入数字进行选择
{
case 1:system("cls"); //先清屏函数，再选择1，进入递归优化一方案
printf("******************************n");
printf("*欢迎进入Fibonacci优化一模块 *n");
printf("******************************n");
printf("请输入要测试数字n");
Fib1();
break;
case 2:system("cls"); //选择2，进入递归优化二方案
printf("******************************n");
printf("*欢迎进入Fibonacci优化二模块 *n");
printf("******************************n");
printf("请输入要测试数字n");
Fib2();
break;
case 3: //选择3，进入递归优化三方案
system("cls");
printf("******************************n");
printf("*欢迎进入Fibonacci优化三模块 *n");
printf("******************************n");
printf("请输入要测试数字n");
Fib3();
break;
case 4:
exit(0); //选择4，退出。
break;
default:
printf("输入有误，请重新输入！！！！n"); //当输入出错时，输出错误信息
Select(); //选择出错时，重新选择
break;
}
}
void Fib1() // 优化一函数
{
int m;
clock_t us1, us2;
char a[5];
scanf_s("%d", &m); //输入数字，进行计算
getchar(); //接收scanf留下的回车
if (m > 45)
{
printf("对不起，值已经越界，请重新输入,不要大于45！！！！n");
Fib1();
}
new1: us1 = clock();
printf("递归优化一函数计算结果:%ldn", Fib_rec1(m));
us2 = clock();
printf("递归优化一函数执行时间%ld毫秒n", us2 - us1);
us1 = clock();
printf("非递归函数计算结果:%ldn", Fib_ite(m));
us2 = clock();
printf("非递归函数执行时间%ld毫秒n", us2 - us1);
printf("************************************n");
printf("* 请选择以下项目： *n");
printf("* a 返回主界面 *n");
printf("* b 退出程序 *n");
printf("* 或者继续键入数字进行计算 *n");
printf("************************************n");
gets_s(a); //继续接收字符串
m = Transfrom(a); //把处理字符函数处理字符的结果给
goto new1; //跳转到排位置
}
void Fib2() //类似优化一
{
int m;
clock_t us1, us2;
char a[5];
scanf_s("%d", &m);
getchar();
{
printf("对不起，值已经越界，请重新输入,不要大于45！！！！n");
Fib2();
}
new2: us1 = clock();
printf("递归优化二函数计算结果:%ldn", Fib_rec2(m));
us2 = clock();
printf("递归优化二函数执行时间%ld毫秒n", us2 - us1);
us1 = clock();
printf("非递归函数计算结果:%ldn", Fib_ite(m));
us2 = clock();
printf("非递归函数执行时间%ld毫秒n", us2 - us1);
printf("************************************n");
printf("* 请选择以下项目： *n");
printf("* a 返回主界面 *n");
printf("* b 退出程序 *n");
printf("* 或者继续键入数字进行计算 *n");
printf("************************************n");
gets_s(a);
m = Transfrom(a);
goto new2;
}
void Fib3() // 类似优化一
{
int m;
clock_t us1, us2;
char a[5];
scanf_s("%d", &m);
getchar();
{
printf("对不起，值已经越界，请重新输入,不要大于45！！！！n");
Fib3();
}
new3: us1 = clock();
printf("递归优化三函数计算结果:%ldn", Fib_rec3(1, 1, m));
us2 = clock();
printf("递归优化三函数执行时间%ld毫秒n", us2 - us1);
us1 = clock();
printf("非递归函数计算结果:%ldn", Fib_ite(m));
us2 = clock();
printf("非递归函数执行时间%ld毫秒n", us2 - us1);
printf("************************************n");
printf("* 请选择以下项目： *n");
printf("* a 返回主界面 *n");
printf("* b 退出程序 *n");
printf("* 或者继续键入数字进行计算 *n");
printf("************************************n");
gets_s(a);
m = Transfrom(a);
goto new3;
}
long Fib_rec1(int n) //递归优化一函数
{
if (n == 0 || n == 1)return 1;
else return(Fib_rec1(n - 1) + Fib_rec1(n - 2));
}
long Fib_rec2(int n) //递归优化二函数
{
if (n == 0 || n == 1)return 1;
if (n == 2)return 2;
if (n == 3)return 3;
else return(Fib_rec1(n - 2) + 2 * Fib_rec1(n - 3) + Fib_rec1(n - 4));
}
long Fib_rec3(int a, int b, int n) //递归优化三函数
{
if (n <= 1)return 1;
if (n == 2)return(a + b);
else Fib_rec3(b, a + b, n - 1);
}
long Fib_ite(int n) // 非递归函数
{
long fib1 = 1, fib2 = 1, fib;
int i;
if (n == 0 || n == 1)return 1;
else
{
for (i = 2; i <= n; i++)
{
fib = fib1 + fib2;
fib1 = fib2;
fib2 = fib;
}
return fib;
}
}
//以下这个函数的意义是当第一次进入某个优化函数时，当把第一次的数字执行完毕时，让用户选择是输入字母选择相应项，还是继续输入数字继续运算
int Transfrom(char a[]) //处理上一个函数给出的字符串
{
char b[3];
if (a[0] >= 65 && a[0] <= 90 || a[0] >= 97 && a[0] <= 122)
//判断字符串首位是否字母，如果字母，进入次级选择函数
SubSelect(a[0]);
else
//数字的话，把数字字符串转化为数字常量，返回处理函数计算。
{
if (atoi(a) < 46)
return(atoi(a));
else
//假如用户的输入数字越界，返回错误信息并让其重新输入
{
printf("对不起，值已经越界，请重新输入,不要大于45！！！！n");
gets_s(b);
Transfrom(b);
}
}
}
void SubSelect(char a)
//次级选择函数，当处理字符串为字母时，传值这里，进行选择，如果有误返回错误信息并跳回主界面
{
switch (a)
{
case 'a':
case 'A': system("cls"); InitMenu(); break;
case 'b':
case 'B':exit(0); break;
default:
printf("输入有误，请重新输入一个值！！！！n");
system("cls");
InitMenu();
break;
}
}
Fibonacci数列递归法和迭代法的模块化测试――注意事项转载请注明
