5.C Functions
===

## 5.1 Introduction
相較於一長串的程式，分割成許多小段程式會更便於開發和維護，而這個方法叫做 ==**分治**== (divide and conquer)

## 5.2 Modularizing Programs in C
函數通常是用來模塊化程式，在 *C standard library* 中有許多已經預先打包好的函數可用，也可自行編寫自己的函數
> 如果在 C standard library 中有的函數就不要自己再寫，用裡面的函數，他的跑得比你快
> [name=小蜜蜂]

- 函數可透過**呼叫函數**來使用
- 函數可呼叫另一個函數(也能呼叫自己)

## 5.3 Math Library Functions
- 函數通常是以 函數名稱 加上右側的 參數 來呼叫，多個參數時，參數間用逗號隔開

printf("%.2f", sqrt(900.0));

- 此函數也可接受指派給 double

double result = sqrt(900.0);

- 參數可用常數或變數表示

printf("%.2f", sqrt(c1 + d * f));
//os. 不要用 c1 d f 這種意義不明的變數名稱呀~

以下列表為本人比較常使用的 math.h 函數~記得include(?~
|函數|描述|
|:--|:--|
|sqrt(x)|開根號|
|pow(x, y)|x^y^|

~反正就是數學有關的都在這裡啦(回傳值都是double)~

## 5.4 Functions
- 函數中宣告的變數為區域變數
- 功能化 (functionalizing) 一個程式有以下優點
1. **分治** 使用分治法更利於開發管理
2. **可重複使用性** 使用現有函數來建立新程式
3. **避免程式碼重複** 要使用時再呼叫函數即可

## 5.5 Function Definitions
- 我們寫的程式都有一個名為 `main` 的函數
### 5.5.1 square Function

#include <stdio.h>

int square(int side); // 函數型態 function prototype

int main(void)
{
    for(int i = 1; i <= 10; i++) {
        printf("%d ", square(i)); // 呼叫函數 function call
    }
    
    puts("");
}

// square 函數定義回傳方形面積
int square(int side) // side 是導入參數 (i) 的複製值
{
    return side * side; // 以 int 型態回傳平方值
}

`1 4 9 16 25 36 49 64 81 100 `

- 函數以第8行的方式呼叫

- 函數定義格式：

回傳型態 函數名稱(參數列表)
{
    做事啊!!
}

回傳型態 (return-value-type) 是傳回呼叫位置的型態 ~廢話~ 如果是`void`就不回傳

- Function Body
- 函數中可以有巢狀，但函數本身不可巢狀 (在函數裡面定義函數，就像不能在main裡定義函數)
- Returning Control from a Function
- 三種回傳方式
1. 沒有回傳值：跑到大括號結束就回去

            return;

2. 有回傳值：函數定義型態資料

            return expression;

3. **main**'s Return Type：回傳 0 以表示程式運行成功 (以前一定要回傳 0，現在預設回傳為 0)

            return 0;

### 5.5.2 maximum Function
與 5.5.1 大同小異，純舉例，略

## 5.6 Funtion Prototypes (function declaration)

int square(int side); // function prototype

- 括號中的 int 預期接收到一個整數值
- square 左方通知編譯器此函數要回傳一個整數
- 編譯器會去比對呼叫函數時的傳入參數與函數定義時
- 參數總數一致
- 參數類型正確
- 參數類型的順序正確，並且
- 回傳值的型態與呼叫時所要求的型態相同
- 前標準 C 沒有使用 prototype 來驗證函數呼叫時傳入的參數，這會導致一些很微妙難找的錯誤
- 放在 main 前面的 prototype (非完整函數)，可使用

    int maximum(int, int, int);

>[name=小蜜蜂]

**函數的強制轉型**
- 參數預設的表示範圍若比導入的範圍大，會強制轉成該型態
- ex. sqrt(4) -> sqrt(4.0) (預設為 double)
- 若從較大的轉入較小的 (ex. double -> int) 可能導致值發生變化
- 若為混和類型的表達模式，編譯器會將其轉成最高類型
- 如果其中有值為 long double，其他的值皆會轉成 long double
- double 和 float 同理

以下列出本人易錯的 printf and scanf
|Data type|printf|scanf|
|:--|:--|:--|
|long double|%Lf|%Lf
|double|%f|==%lf==|
|unsigned short|%hu|%hu|
|short|%hd|%hd|
- 只有指派 (int a = b; // b is double) 或使用強制轉換運算符((int)b)才能由高類型轉到低類型
- 注意傳入的函數參數是否會導致強制轉型
- ex. square(4.5) 值為 16，非 20.25
- 如果一開始在 prototype 沒有宣告參數型態，編譯器會以遇到第一個有參數的函數為準 (不論是在呼叫函數時，還是在定義函數時)

## 5.7 Funtion Call Stack and Stack Frames
- 函數呼叫時會採用 **stack**，以便回到上一層呼叫函數的位置
### stack(堆疊)
- 後進先出或先出後進 last-in, first-out (LIFO) data structure
- 相對於 LIFO ， queue 為先進先出 (FIFO)
- fuction call stack (program execution stack) 會在後台執行函數呼叫及回傳事宜
- push and pop
- 上圖的 1 2 3 為 stack frame，包含回傳位址
- 正在執行的(最新push進的)程式會在==最上方==
- 當函數執行時，其中的 automatic variables 會持續存在，直到函數結束 (變數的生命週期，始於宣告終於 '}')
- 因為記憶體有限，如果 stack frames 太多，會導致 **stack overflow**
- ex. 以 square() 函數為例
1. OS 呼叫 main 會 push 一個 stack frame 來存 main位址(R1) 以及 automatic variable
2. push 另一個 stack frame 給 square 存位址(R2) 以及 automatic variable
3. pop square 並回傳位址(R2) ，並拋棄 square 的 automatic variable
4. pop main 並回傳位址(R1) 給 OS ，並拋棄 main 的 automatic variable

## 5.8 Headers
- 這個小節裡面有張表格說明各種標準函數，在這裡就不一一列出，在第204、205頁
- 標準函數需用<>
- 自訂的函數需用""，並且副檔名須為.h

#include <stdio.h>    // 標準函式庫
#include "square.h"   // 自訂函式庫

## 5.9 Passing Arguments By Value and By Reference
- pass-by-value (傳值)
- 被呼叫的函數並不會改動到呼叫者的變數
- pass-by-reference (傳址)
- 需要修改原變數時使用

在第七章指標會談到更多如何傳址的方法，目前只專注於傳值 ~(課本說的)~

## Random Number Generation

#include <stdlib.h> // rand在這裡~

- rand 函數會隨機生成 0 ~ RAND_MAX (最低32767) 之間的數
- 以下為隨機印出範圍 1~6 的數

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    for (unsigned int i = 1; i <= 20; ++i) {
        // 隨機挑選 1~6 之間的數字並印出
        printf("%10d", 1 + (rand() % 6));
    
        if (i % 5 == 0) {
            puts("");
        }
    }
}

- 我們可以用 rand() % 6 來生成 0~5 之間的整數，此動作稱為縮放 (scaling)，而 6 稱為比例因子 (scaling factor)

### 自定義種子碼
- 在沒有用`srand`生成種子碼前，以上程式每次跑結果都一樣 (偽隨機)
- `srand` 接受 unsigned int 當總子碼

#include <stdlib.h>
#include <stdio.h>

int main(void)
{
    usinged int seed;
    pritnf("%s", "Enter seed: ");
    scanf("%u", &seed);
    
    srand(seed); // 設定種子碼
    
    ... // print the random number
}

- 相同總子碼出來的結果相同
### 用時間當種子碼

#include <stdlib.h> // for srand and rand
#include <time.h>   // for time
...
srand(time(NULL))

- time 函數會回傳自1月午夜以來經過的秒數

>ps. 課本廢話太多，給大家整理取一定範圍內亂數的公式
>```c=
>rand() % (max - min + 1) + min;
>```
>>[name=drop]

## 5.11 Example: A Game of Chance; Introducing enum
- enum 使用方法

#include <stdio.h>

enum Status { CONTINUE, WON, LOST};

int main(void)
{
    ...
    enum Status gameStatus;
    ...
    switch(sum){
        case 7:
            gameStatus = WON;
            break;
        ...
    }
    ...
    if (WON == gameStatus) {
        puts("Player wins");
    }
    ...
}

- 可增加程式可讀性
- 可維護性高，因為 enum 是從 0 開始遞增
- enum 中標識符(名稱)須是唯一的，但值可重複
- 類似於 `#define` 皆是定義常數，非變數
>完整程式碼、此遊戲的設定以及非enum的解說在課本第 210~214 頁

## 5.12 Storage Classes
- auto, register, extern and static 此四項為存儲類說明符 (存哪裡，活多久)
- 變數在被創建後，活躍於該區塊，並在程序退出該區塊時被銷毀 ~翻的不是很好，有沒有人有更好的說法?~
- 存儲類說明符分為
- 自動存儲持續時間 automatic storage duration (只在自家裡面活)
- 靜態存儲時間 static storage duration (我永遠都活著，但不代表你一定看的到我)

|存儲類說明符|翻譯|解釋|
|:--:|:--:|:--|
|auto|自動的|宣告一個區域變數|
|register|暫存器的|將變數存在CPU暫存器中|
|extern|外部的|在a.c中要使用b.c中的函數時，在a.c中做外部聲明|
|static|靜態的|只初始化一次，並一直存在|

[更多詳細資訊](https://www.twblogs.net/a/5d4d7010bd9eee5327fc60c0)

### Local Variables (區域變數)
- 只有變數有自動持續存儲時間
- 默認為 auto
- 很少使用 auto 修飾
- 只存在於被宣告的區塊內
### Static Storage Class (靜態存儲類)
- extern, static 兩者用來宣告靜態函數與變數
- 從程式一開始到結束之前都存在
- 僅分配及初始化一次
:::warning
**這不代表你在哪裡都可以看的到，存在時間與存取範圍是兩回事**
:::
- **Global variables (全域變數)**
- 預設全域變數為 extern
- 放在任何函數之外來宣告
- 整個程式運行中皆會保存值
>沒事別用全域變數
>[name=小蜜蜂]
- static 宣告方式

static int count = 1;

## 5.13 Scope Rules
- 標識符的範圍是程序中可以引用標識符的部分。
- scope 分為四個部分
- function scope
- labels(某某:) 是唯一具有 function scope 的標識符
- lables 用於 switch (其中的 case) 以及 goto
- lables 隱藏(information hiding)於定義他們的函數中
- 實施最小權限原則(principle of least privilege)的手段 (權限不夠就限制你能訪問的內容)
- file scope
- 在任何函數之外宣告的標識符
- 在文件結束之前都可看到
- 經典例子 全域變數、函數定義、函數原型(prototype)
- block scope
- 在區塊內宣告的標識符
- 終止於右大括號 ( } )
- 若區塊為巢狀，變數名稱又一樣，會以較內部的為準

        {
            int a = 0;
            {
                int a = 10;
                printf("%d\n", a); // print 10，以區塊內為準
            }
            printf("%d\n", a); // print 0，上個區塊的變數已經結束
        }

>盡量用不同的名稱，不要讓自己confuse，也不要confuse別人，知道嗎?
>[name=老葉]
- 經典例子 區域變數
- 就算是 static 也有 block scope 特性 (時間是時間，空間是空間)
- function-prototype scope
- 導入函數時參數的命名 是唯一具有 function-prototype scope 的標識符
- prototype 不需要變數名稱，有寫的話會忽略 (意思是叫你定義函數的時候再寫)

        int QQ(int , char[]); // prototype
        
        int main(void){
            QQ(87, "eighty seven");
            return 0;
        }
        
        int QQ(int num, char trans[]){
            ...
        }

- prototype 中導入參數的名稱可以在其他地方用

更多舉例在課本 217~219

## 5.14 Recursion
>用遞迴要做的第一件事就是要找==什麼時候停止==
>[name=老葉]
- base case(s) 裡的函數只知道怎麼解最簡單的問題
- base case 被呼叫時，函數會簡單回傳一個結果
- 若叫困難的情況被函數呼叫時，函數通常會將問題分成兩個概念，函數知道怎麼做&函數不知道怎麼做
- 函數不知道怎麼做的部分需要被分成更接近base case的問題，以此遞迴
- 遞迴函數包含一個return值，以回傳結果或較簡單問題的子結果給呼叫者

>課本解釋得太複雜，我簡單來說
>遞迴就是一個把大問題分成兩個小問題的解法，通常會成二元樹狀，直到 base case
>ps. 遞迴沒想像中好，小心TLE，不信的話用遞迴寫費氏數列找找看第60個
>[name=drop]

### Recursively Calculating Factorials

factorial = 1;
for(counter = number; counter >= 1; --counter)
    factorial *= counter;

階層 for 版本

#include <stdio.h>
usigned long long int factorial(unsigned int number);

int main(void)
{
    for (unsigned int i = 0; i <= 21; ++i) {
        printf("%u! = %11u\n", i, factorial(i));
    }
}

unsigned long long int factorial(unsigned int number)
{
    if (number <= 1) {
        return 1;
    }
    else {
        return (number * factorial(number - 1));
    }
}

階層 遞迴版
- 解題技巧同上
- long long int 可能還是不夠記，未來在 C++ 的 classes 可以自訂新的類別，想存多少存多少

## 5.15 Example Using Recursion: Fibonacci Series
`0, 1, 1, 2, 3, 5, 8, 13, 21,...`
fibonacci(0) = 0
fibonacii(1) = 1
fibonacii(n) = fibnacii(n-1) + fibonacii(n-2)

#include <stdio.h>

unsigned long long int fibonacci(unsigned int n);

int main(void)
{
    unsigned int number;
    
    printf("%s", "Enter an interger: ");
    scanf("%u", &number);
    
    unsigned long long int result = fibonacci(number);
    
    printf("Fibonacii(%u) = %11u\n", number, result);
}

unsigned long long int fibonacii(unsinged int n)
{
    if (0 == n || 1 == n) {
        return n;
    }
    else {
        return fibonacci(n - 1) + fibonacii(n - 2);
    }
}

- 出於優化原因，大多運算子沒有規定一定要從左算到右，不應假設運算 a + b 時一定為 a+b 或者 b+a ，可能會先執行a或者b函數，在某些運算中，這會產生副作用
>編寫依賴於除 &&、||、?: 和逗號 (,) 運算符以外的運算符的操作數的計算順序的程序可能會導致錯誤，因為編譯器可能不一定按照您期望的順序計算操作數。
>[name=小蜜蜂]
### Exponential Complexity
- 警告遞迴函數的時間複雜度
- 遞迴費氏數列時間複雜度為 O( 2^n^ ) (指數複雜度)
- 第 20 個斐氏數將需要 2^20^ 或大約一百萬次遞迴
- 第 30 個斐氏數將需要 2^30^ 或大約十億次遞迴
- 更好的算法統稱為 Algorithms(演算法)

## 5.16 Recursion(遞迴) vs. Iteration(迭代)
- 兩者皆是 control statement ，迭代用 iteration statement，遞迴用 selection statement
- 兩者皆包含重複 ，迭代用 iteration statement，遞迴用重複呼叫自己
- 兩者皆有停止狀態，迭代止於條件不符合，遞迴視 base case
- 迭代的計數器每次逐漸接近終止，遞迴不斷產生原始問題的更簡單版本，直到達到 base case
- 兩者皆可無限迴圈，遞迴的無限迴圈情況發生於無法收斂到 base case，兩者發生時很可能是邏輯錯誤
- 遞迴的負面影響
- 反覆呼叫函數導致
- 耗時
- 佔空間
>遞迴能解迭代一定能解，選擇遞迴的原因是因為用遞迴更容易理解與除錯，並且迭代的解法可能不好想
>[name=小蜜蜂]

>將大型程式劃分為函數可以促進良好的軟體工程。但較沒有函數的單體程式來比，會呼叫大量的函數，導致消耗CPU上的實行時間
>雖然單體程式性能可能更好，但更難編寫、測試、除錯、維護和發展
>[name=小蜜蜂]

## 5.17 Secure C Programming
在 5.10 中所介紹了 rand 函數，但 C 標準函式庫不提供安全的隨機數生成器，無法保證生成的隨機序列的品質，並且已知某些實現會生成具有令人不安的非隨機低階位的序列，需要建立隨機數的工業級應用程式時，需針對平台研究推薦使用的函數。

# Chapter 5 結束

###### tags: `程設好難` `學校門口大樹石頭下` `他的課就很好睡阿`
<style>
.navbar-brand::after { content: " × 老葉的程式設計"; }
</style>