前言：

上一篇函數1我們已將了解了函數的大部分知識，接下來我們繼續學習剩下的知識

1.函數的聲明和定義

1.1 函數聲明：

告訴編譯器有一個函數叫什么，參數是什么，返回類型是什么。但是具體是不是存在，函數聲明決定不了。函數的聲明一般出現在函數的使用之前。要滿足先聲明后使用。函數的聲明一般要放在頭文件中的。

6.2 函數定義：

函數的定義是指函數的具體實現，交待函數的功能實現。

test.h的內容放置函數的聲明

(資料圖片)

#ifndef __TEST_H__#define __TEST_H__//函數的聲明int Add(int x, int y);#endif //__TEST_H__

test.c的內容

放置函數的實現

#include "test.h"http://函數Add的實現int Add(int x, int y){ return x+y;}

這種分文件的書寫形式，在三字棋和掃雷的時候，分模塊來寫。（后面詳細講解）

2. 函數遞歸

2.1 什么是遞歸？

程序調用自身的編程技巧稱為遞歸（ recursion）。

遞歸做為一種算法在程序設計語言中廣泛應用。 一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。遞歸的主要思考方式在于：把大事化小

2.2 遞歸的兩個必要條件

存在限制條件，當滿足這個限制條件的時候，遞歸便不再繼續。

每次遞歸調用之后越來越接近這個限制條件。

2.2.1 練習1：（畫圖講解）

接受一個整型值（無符號），按照順序打印它的每一位。

例如：

輸入：1234，輸出 1 2 3 4.

遞歸在c語言中是一個非常復雜的概念，但是遞歸的作用有很大，本題題意參考圖解，大致意思是print函數的自我調用

參考代碼：

void print(int n){ if(n>9) { print(n/10); } printf("%d ", n%10);}int main(){ int num = 1234; print(num); return 0;}

2.2.2 練習2

編寫函數不允許創建臨時變量，求字符串的長度。

//編寫函數不允許創建臨時變量，求字符串的長度。//遞歸的方法// my_strlen("bit")//1+my_strlen("it")//1+1+my_strlen("t")//1+1+1+my_strlen("")// 1+1+1+0// 3int Strlen(const char* str){  if (*str == "\0")    return 0;  else    return 1 + Strlen(str + 1);}int main(){  char* p = "bit";  int len = Strlen(p);  printf("%d\n", len);  return 0;}

3.遞歸與迭代

3.1 練習3：

求n的階乘。（不考慮溢出）

參考代碼：

每調用一次fac2(n - 1)函數，n的值都會減一，直到n=1時不在調用然后層層函數開始返回

//求n的階乘，遞歸的方法int fac2(int n){  if (n <= 1)  {    return 1;  }  else  {    return n * fac2(n - 1);  }}int main(){  int a = 0;  scanf("%d", &a);  int ret = fac2(a);  printf("%d\n", ret);  return 0;}

3.2 練習4：

求第n個斐波那契數。（不考慮溢出）

參考代碼：

遞歸求斐波那契數列：1 1 2 3 5 8 13 21 34 55·····即后一個數是前兩個數之和

//遞歸求斐波那契數列：1 1 2 3 5 8 13 21 34 55·····即后一個數是前兩個數之和int fib(int n){  if (n <= 2)    return 1;  else    return fib(n - 1) + fib(n - 2);}int main(){  int n = 0;  scanf("%d", &n);  int ret=fib(n);  printf("%d\n", ret);  return 0;}

但是我們發現有問題；

在使用 fib 這個函數的時候如果我們要計算第50個斐波那契數字的時候特別耗費時間。使用 factorial 函數求10000的階乘（不考慮結果的正確性），程序會崩潰。

為什么呢？

我們發現 fib 函數在調用的過程中很多計算其實在一直重復。

如果我們把代碼修改一下：

int count = 0;//全局變量int fib(int n){ if(n == 3) count++; if (n <= 2)          return 1;    else    return fib(n - 1) + fib(n - 2);}

最后我們輸出看看count，是一個很大很大的值。

那我們如何改進呢？

在調試 factorial 函數的時候，如果你的參數比較大，那就會報錯： stack overflow（棧溢出）這樣的信息。系統分配給程序的?？臻g是有限的，但是如果出現了死循環，或者（死遞歸），這樣有可能導致一直開辟?？臻g，最終產生?？臻g耗盡的情況，這樣的現象我們稱為棧溢出。

那如何解決上述的問題：

將遞歸改寫成非遞歸。使用static對象替代 nonstatic 局部對象。在遞歸函數設計中，可以使用 static 對象替代nonstatic 局部對象（即棧對象），這不僅可以減少每次遞歸調用和返回時產生和釋放 nonstatic 對象的開銷，而且 static 對象還可以保存遞歸調用的中間狀態，并且可為各個調用層所訪問

比如，下面代碼就采用了，非遞歸的方式來實現：

//求n的階乘int factorial(int n){        int result = 1;        while (n > 1)       {             result *= n ;             n -= 1;       }        return result;}//求第n個斐波那契數int fib(int n){     int result;     int pre_result;     int next_older_result;     result = pre_result = 1;     while (n > 2)     {           n -= 1;           next_older_result = pre_result;           pre_result = result;           result = pre_result + next_older_result;     }     return result;}

提示：

許多問題是以遞歸的形式進行解釋的，這只是因為它比非遞歸的形式更為清晰。但是這些問題的迭代實現往往比遞歸實現效率更高，雖然代碼的可讀性稍微差些。當一個問題相當復雜，難以用迭代實現時，此時遞歸實現的簡潔性便可以補償它所帶來的運行時開銷。

4.函數遞歸的幾個經典題目：

4.1 漢諾塔問題

感興趣的可以研究一下

//漢諾塔void hannuo(int n, char a, char b, char c)//char a, char b, char c三個只代表形參并非真是值，而實參是傳遞過來的是真實值{                   if (n == 1)//如果只有一個盤子，直接把盤子從a->c  {    printf(" %c->%c ", a, c);  }  else//如果有多個盤子  {    hannuo(n - 1, a, c, b);//先把n-1個盤子從a通過c移動到b    printf(" %c->%c ", a, c);//這是n-1個盤子已經挪到了b，只需要把a上剩的盤子移動到c上即可    hannuo(n - 1, b, a, c);//然后再將b上的盤子通過a移動到c上  }}int main(){  int n = 0;  scanf("%d", &n);  hannuo(n,"a","b","c");//這些都是實參  return 0;}

留言：

歡迎留言交流，喜歡就點贊支持一下吧