目錄
1.C語言中函數的分類：
1.1 庫函數
1.2 自定義函數
例1：寫一個函數可以找出兩個整數中的最大值
例2：寫一個函數可以交換兩個整形變量的内容
1.2.1***需要學會找bug的過程：調試( F10)
2.函數的參數
2.1 實際參數（實參）
2.2 形式參數（形參）
3.函數的調用：
3.1 傳值調用
3.2 傳址調用
4.函數的嵌套調用和鍊式通路
4.1 嵌套調用
4.2 鍊式通路
5.函數的聲明和定義
5.1 函數聲明
5.2 函數定義
6.函數遞歸
6.1 遞歸的兩個必要條件
補充：在記憶體中的區域劃分
6.1.1 練習1：接受一個整型值（無符号），按照順序列印它的每一位。（用遞歸解決）
6.1.2 練習2：編寫函數不允許建立臨時變量，求字元串的長度。
6.1.3 練習3：用遞歸求n的階乘(不考慮溢出)。
6.1.4 練習4：求第n個斐波那契數。（不考慮溢出）。
1.C語言中函數的分類：
1.庫函數
2.自定義函數
1.1 庫函數
為了支援可移植性和提高程式的效率，C語言的基礎庫中提供了一系列類似的庫函數（由常用的功能（如列印資料，求字元串長度，輸入資料 等）用C語言封裝而成），友善程式員進行軟體開發。
推薦一個學習庫函數的網站：www.cplusplus.com
打開後可查詢每個頭檔案包含的庫函數 以及庫函數的用法、示例等
如：查詢strcpy函數:
注： 但是庫函數必須知道的一個秘密就是：使用庫函數，必須包含 #include 對應的頭檔案。
簡單的總結，C語言常用的庫函數都有：
IO函數
字元串操作函數
字元操作函數
記憶體操作函數
時間/日期函數
數學函數
其他庫函數
庫函數需要全部記住嗎？
并不是。但需要學會查詢工具的使用：
MSDN(Microsoft Developer Network)
www.cplusplus.com http://en.cppreference.com（英文版）
http://zh.cppreference.com（中文版）
1.2 自定義函數
自定義函數和庫函數一樣，有函數名，傳回值類型和函數參數。 但是不一樣的是這些都是我們自己來設計。這給程式員一個很大的發揮空間。
函數的基本組成：
ret_type fun_name(para1, * )
{
statement; //語句項
}
//ret_type 傳回類型
//fun_name 函數名
//para1 函數參數
例1：寫一個函數可以找出兩個整數中的最大值
#include <stdio.h>
int get_max(int x, int y)
{
return (x>y)? (x):(y);
}
/*或者
int get_max(int x, int y)
{
int z = 0;
if (x > y)
z = x;
else
z = y;
return z;
*/
int main()
{
int num1 = 0;
int num2 = 0;
scanf("%d %d", &num1, &num2);
//get_max為自己建立的自定義函數
int max = get_max(num1, num2);
printf("max = %d\n", max);
return 0;
}
例2：寫一個函數可以交換兩個整形變量的内容
先看一個錯誤執行個體：
//錯誤執行個體
#include <stdio.h>
//bug：結果并沒有交換
//找bug的過程叫：調試 F10 按F10一步一步向下走，遇到函數時按F11進入函數内部
void Swap(int a, int b)
{
int temp = 0;
temp = a;
a = b;
b = temp;
}
int main()
{
int num1 = 0;
int num2 = 0;
scanf("%d %d", &num1, &num2);
Swap(num1, num2);
printf("num1 = %d num2 = %d\n",num1,num2); /num1與num2的值并未發生交換
return 0;
}
1.2.1***需要學會找bug的過程：調試( F10)
按F10一步一步向下走，遇到函數時按F11進入函數内部
在錯誤執行個體中:
可見，當執行swap函數後，a與b的值交換了，而num1和num2的值并未交換
再看a，b，num1，num2的位址情況：
當把參數num1，num2傳給a，b時，a和b獨立開辟了空間，swap函數确實交換了a與b的值，但由于a，b與num1，num2并不在同一個空間，是以num1和num2的值沒有随着ab改變。
示例中的num1和num2 被稱為實參 - 實際參數 a和b被稱為形參 - 形式參數
當實參傳給形參的時候，形參是實參的一份臨時拷貝 ==》對形參的修改不會影響實參
那麼如何正确完成該示例呢？
用指針： 通過swap函數傳入num1，num2的位址。pnum1存入的num1的位址，進而使pnum1指向num1；同理，pnum2指向num2。由此使swap函數内外産生聯系。
//正确示例
#include <stdio.h>
void Swap(int* pnum1, int* pnum2)
{
int temp = *pnum1;
*pnum1 = *pnum2;
*pnum2 = temp;
}
int main()
{
int num1 = 0;
int num2 = 0;
scanf("%d %d", &num1, &num2);
Swap(&num1, &num2);
printf("num1 = %d num2 = %d\n",num1,num2);
return 0;
}
總結：當在函數内部需要改變外部的某些變量的時候，需要使用指針(函數傳入變量的位址進入)
2. 函數的參數
2.1實際參數（實參）
真實傳給函數的參數，叫實參。
實參可以是：常量、變量、表達式、函數等。
無論實參是何種類型的量，在進行函數調用時，它們都必須有确定的值，以便把這些值傳送給形 參。
2.2形式參數（形參）
形式參數是指函數名後括号中的變量，因為形式參數隻有在函數被調用的過程中才執行個體化（配置設定内 存單元），是以叫形式參數。
形式參數當函數調用完成之後就自動銷毀了。是以形式參數隻在函數中有效。
形參執行個體化之後其實相當于實參的一份臨時拷貝。
練習：用函數實作二分查找
//實作函數在arr數組中查找k
//若找到傳回下标，找不到傳回-1(因為數組下标可以為0，是以查找失敗傳回值采用-1)
#include <stdio.h>
int binary_search(int arr[], int k, int sz)
{
int left = 0;
int right = sz - 1;
while (left <= right)
{
int mid = (left + right) / 2;
if (arr[mid] > k)
right = mid - 1;
else if (arr[mid] < k)
left = mid + 1;
else
return mid;
}
return -1;
}
int main()
{
int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
int sz = sizeof(arr) / sizeof(arr[0]);
int k = 7; //k為被查找的數字
int ret = binary_search(arr, k, sz);
if (ret == -1)
printf("未找到指定元素");
else
printf("找到了，該元素下标是：%d", ret);
return 0;
}
需注意的是，如果在binary_search函數内部用sz = sizeof(arr) / sizeof(arr[0])來計算數組長度，會查找失敗：
#include <stdio.h>
int binary_search(int arr[], int k)
{
int sz = sizeof(arr) / sizeof(arr[0]);
int left = 0;
int right = sz - 1;
while (left <= right)
{
int mid = (left + right) / 2;
if (arr[mid] > k)
right = mid - 1;
else if (arr[mid] < k)
left = mid + 1;
else
return mid;
}
return -1;
}
int main()
{
int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
int k = 7; //k為被查找的數字
int ret = binary_search(arr, k);
if (ret == -1)
printf("未找到指定元素");
else
printf("找到了，該元素下标是：%d", ret);
return 0;
} //未找到指定元素
查找失敗的原因在于，當在向binary_search函數傳入arr時，實際上隻是向該函數中傳入了arr數組中第一個元素的位址，此時sizeof(arr) = 4，是以導緻了查找失敗
當數組作為傳參時，傳入的是數組首字元的位址
是以當函數中需要求數組元素個數的時候，在函數外部求好後，再傳入函數中
3.函數的調用：
3.1 傳值調用
函數的形參和實參分别占有不同記憶體塊，對形參的修改不會影響實參。
3.2 傳址調用
傳址調用是把函數外部建立變量的記憶體位址傳遞給函數參數的一種調用函數的方式。
這種傳參方式可以讓函數和函數外邊的變量建立起真正的聯系，也就是函數内部可以直接操作函數外部的變量。
例：寫一個函數，每調用一次這個函數，就會将 num 的值增加1
#include <stdio.h>
void Add(int* p)
{
*p = *p + 1 ;
}
int main()
{
int num = 0;
Add(&num);
printf("num = %d\n", num); //1
Add(&num);
printf("num = %d\n", num); //2
return 0;
}
4.函數的嵌套調用和鍊式通路
函數和函數之間可以根據實際的需求進行組合的，也就是互相調用的。
4.1 嵌套調用
函數可以嵌套調用，但是不能嵌套定義
#include <stdio.h>
void new_line()
{
printf("hehe\n");
}
void three_line()
{
int i = 0;
for (i = 0; i < 3; i++)
{
new_line();
}
}
int main()
{
three_line();
return 0;
}
4.2鍊式通路
把一個函數的傳回值作為另外一個函數的參數
#include <stdio.h>
int main()
{
printf("%d", printf("%d", printf("%d", 43))); //4321
return 0;
在MSDN中，可以查到，printf函數的傳回值為列印的字元的個數，發生錯誤的時候傳回負值
5.函數的聲明和定義
5.1 函數聲明
1. 告訴編譯器有一個函數叫什麼，參數是什麼，傳回類型是什麼。但是具體是不是存在，函數 聲明決定不了。
2. 函數的聲明一般出現在函數的使用之前。要滿足先聲明後使用。
3. 函數的聲明一般要放在頭檔案中的。
教科書中的寫法：(一般不采用該寫法)
#include <stdio.h>
//聲明一下
//聲明函數 - 告訴編譯器有一個函數，名叫ADD，2個參數都是int類型，函數傳回類型是int
int Add(int x, int y);
int main()
{
int a = 10;
int b = 20;
int ret = Add(a, b);
printf("%d\n", ret);
return 0;
}
//函數定義
int Add(int x, int y)
{
int z = x + y;
return z;
}
工程中的寫法：
5.2 函數定義
函數的定義是指函數的具體實作，交待函數的功能實作。
6.函數遞歸
程式調用自身的程式設計技巧稱為遞歸（ recursion）。
遞歸做為一種算法在程式設計語言中廣泛應用。
一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法。
它通常把一個大型複雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解， 遞歸政策 隻需少量的程式就可描述出解題過程所需要的多次重複計算，大大地減少了程式的代碼量。
遞歸的主要思考方式在于：把大事化小
6.1遞歸的兩個必要條件
基準情形：存在限制條件，當滿足這個限制條件的時候，遞歸便不再繼續。
不斷推進：每次遞歸調用之後越來越接近這個限制條件。
補充：在記憶體中的區域劃分
每一次函數調用都需要配置設定空間。
是以在寫遞歸函數的時候一定要注意兩個必要條件，否則可能出現棧溢出的現象。
6.1.1 練習1：接受一個整型值（無符号），按照順序列印它的每一位。（用遞歸解決）
分析，當輸入1234時，需要用函數輸出1 2 3 4 ，那麼用遞歸的化簡思想：
假設自定義列印函數為print，則：
1.當傳入數字大于等于兩位（>9），繼續劃分
2.當劃分至個位，列印
圖示為：
代碼如下：
#include <stdio.h>
void print(int n)
{
if (n > 9)
{
print(n / 10);
}
printf("%d ", n % 10);
}
int main()
{
unsigned int num = 0;
scanf("%d", &num);
print(num);
return 0;
}
6.1.2 練習2：編寫函數不允許建立臨時變量，求字元串的長度。
建立臨時變量(count)的版本：
#include <stdio.h>
int my_strlen(char* str)
{
int count = 0;//計數器
while (*str != '\0')
{
count++;
str++;
}
return count;
}
int main()
{
char arr[] = "abcdef";
int len = my_strlen(arr);//傳入的是首字元的位址，是以用字元指針接收
printf("%d\n", len); //6
return 0;
}
不建立臨時變量的版本(遞歸版本)：
遞歸思路：
#include <stdio.h>
int my_strlen(char* str)
{
if (*str != '\0')
return 1 + my_strlen(str + 1);
else
return 0;
}
int main()
{
char arr[] = "abcdef";
int len = my_strlen(arr);//傳入的是首字元的位址，是以用字元指針接收
printf("%d\n", len);
return 0;
}
6.1.3 練習3：用遞歸求n的階乘(不考慮溢出)。
遞歸思路：
n! = n * (n-1) , n>= 2;
n! = 1 , n<= 1;
int Fac(int a)
{
if (a > 1)
return a * Fac(a - 1);
else
return 1;
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = Fac(n);
printf("%d\n", ret);
return 0;
}
6.1.4 練習4：求第n個斐波那契數。（不考慮溢出）。
斐波那契數列：1 1 2 3 5 8 13 21 34 55...
規律：第n個數字等于n前兩個數字之和
Fib(n) = 1, n <= 2
Fib(n) = Fib(n - 1) + Fib(n - 2), n <= 2
遞歸思路：
#include <stdio.h>
int Fib(int a)
{
if (a > 2)
return Fib(a - 1) + Fib(a - 2);
else
return 1;
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = Fib(n);
printf("%d\n", ret);
return 0;
}
無減枝操作的斐波那契遞歸代碼效率很低下，如果參數比較大，那就會報錯： stack overflow（棧溢出） 這樣的資訊。
系統配置設定給程式的棧空間是有限的，但是如果出現了死循環，或者（死遞歸），這樣有可能導緻一 直開辟棧空間，最終産生棧空間耗盡的情況，即棧溢出。
那如何解決上述的問題：
1. 将遞歸改寫成非遞歸。
2. 使用static對象替代 nonstatic 局部對象。
在遞歸函數設計中，可以使用 static 對象替代 nonstatic 局部對象（即棧對象），這不僅可以減少每次遞歸調用和傳回時産生和釋放 nonstatic 對象的開銷，而且 static 對象還可以保 存遞歸調用的中間狀态，并且可為 各個調用層所通路。
非遞歸版本：
第一次：
a = 1，b = 1，c = a + b
第二次：
a = b，b = c，c = a + b
是以非遞歸代碼為：
//更簡潔的代碼
#include <stdio.h>
int Fib(int n)
{
int a = 1;
int b = 1;
int c = 1;
while(n > 2)
{
c = a + b;
a = b;
b = c;
n--;
}
return c;
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = Fib(n);
printf("%d\n", ret);
return 0;
}
//初始構思的代碼
#include <stdio.h>
int Fib(int n)
{
int a = 1;
int b = 1;
int c = 1;
int i = 0;
if (n <= 2)
return 1;
for (i = 0; i < n - 2; i++) //因為邏輯上當n > 2時，才開始循環，是以n=3對應第1次循環 是以
//判斷條件為i < n - 2
{
a = b;
b = c;
c = a + b;
}
return c;
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = Fib(n);
printf("%d\n", ret);
return 0;
}
小結：
1. 許多問題是以遞歸的形式進行解釋的，這隻是因為它比非遞歸的形式更為清晰。
2. 但是這些問題的疊代實作往往比遞歸實作效率更高，雖然代碼的可讀性稍微差些。
3. 當一個問題相當複雜，難以用疊代實作時，此時遞歸實作的簡潔性便可以補償它所帶來的運作時開銷。