本文介紹Fibonacci數列用遞歸法和迭代法區別，重點在於本文把遞歸法進行了優化，用二叉樹，三叉樹，尾歸法分別來設計遞歸算法並和迭代法進行比較，而且這個代碼把這些功能做了模塊化，方便使用。（c語言，vs2013編譯器）（文章後會附代碼）
二叉樹遞歸算法函數名Fib_rec1.
三叉樹遞歸算法函數名Fib_rec2.
尾歸法遞歸算法函數名Fib_rec3.
遞迭代法算法函數名Fib_ite.
工具/原料
vs或者vc++
方法/步驟
程序主界面，
模塊一為二叉樹遞歸算法和迭代法比較
模塊二為三叉樹遞歸算法和迭代法比較
模塊三為尾歸法遞歸算法和迭代法比較
數字4退出
主界面錯誤輸入測試
次級模塊界面，輸入fiboncci位數開始測試
定義了越界值，非法輸入時報錯
程序可在次級界面選擇繼續輸入數字測試，或者返回主界面，或者退出
代碼如下
#include
#include
#include
//函數聲明，後面介紹函數功能
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("遞歸優化一函數計算結果:%ld\n", Fib_rec1(m));
us2 = clock();
printf("遞歸優化一函數執行時間%ld毫秒\n", us2 - us1);
us1 = clock();
printf("非遞歸函數計算結果:%ld\n", 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("遞歸優化二函數計算結果:%ld\n", Fib_rec2(m));
us2 = clock();
printf("遞歸優化二函數執行時間%ld毫秒\n", us2 - us1);
us1 = clock();
printf("非遞歸函數計算結果:%ld\n", 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("遞歸優化三函數計算結果:%ld\n", Fib_rec3(1, 1, m));
us2 = clock();
printf("遞歸優化三函數執行時間%ld毫秒\n", us2 - us1);
us1 = clock();
printf("非遞歸函數計算結果:%ld\n", 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;
}
}