函數與遞迴

函數：

意思是指「有傳回值的副程式」，通常應用在一段程式重複出現多次，我們可以把它獨立成函數，以減少程式撰寫工作,易於維護,並增加程式的可讀性。

格式：

傳回值型態　函數名稱(參數1，參數2……)

{

函數的本體

}

傳回值型態：可以在函數名稱前加上型別宣告，其用來宣告其傳回值的資料型別。若無傳回值，則宣告其型別為void。

函數名稱：開頭第一字元不可以是數字，其餘部份由英文字母、數字…構成。

參數：函數名稱後緊接著"( )"符號，不管是否有參數值，都一定要有此符號。

範例1：

#include <stdio.h>
int addFun(int x, int y) {
    return x + y;
}
void main() {
    int a = 10, b = 20, r;
    r =  addFun(a, b);
    printf("%d + %d = %d \n", a, b, r);
}

範例2：

#include <stdio.h>
void list(void) {
    printf("不傳參數、不傳回值\n");
}
int main( ) {
    list();
}

範例3：

#include <stdio.h>
int add_Fun(void) {
    int a = 5, b = 10, z;
    z = a + b;
    return z;
}
int main() {
    int c;
    c = add_Fun();
    printf("The result is %d \n", c);
}

範例4：

#include <stdio.h>
void subtract_Fun(int i, int j) {
    print(" %d - %d = %d\n", i, j, i - j);
}
int main() {
    int a = 14, b = 15;
    subtract_Fun(a, b);
}

範例5：

#include <stdio.h>
int multiply_Fun(int x, int y) {
    return x * y;
}
int main() {
    int a=2, b=19;
    printf("%d * %d = %d \n", a, b, multiply_Fun(a, b));
    printf("%d\n", multiply_Fun(a, b) + multiply_Fun(2*a, 2*b));
    printf("%d\n", multiply_Fun(multiply_Fun(a, b), b));
}

為了讓compiler能夠正確編譯函數呼叫,在呼叫函數A前必須要先做定義函數A,因此前面幾個範例內的函數都放在main的前面。某些時候由於遞迴呼叫或是其他原因,可能在定義函數A前就要用到該函數,則可以用以下的方法來解決:

#include <stdio.h>
double multiply_Fun(double, double);
int main() {
    double a=2, b=19, c;
    c = multiply_Fun(a, b);
    printf("%lf * %lf = %lf \n", a, b, c);
}
double multiply_Fun(double x, double y) {
    return x * y;
}

第二行只是定義multiply_Fun所需要的參數和傳回值。如果用到系統的函數庫,就要include相關的.h檔,其原因也是如此。讀者可以找找你所用開發環境內的stdio.h長甚麼樣子。

參數傳遞

C語言定義參數傳遞的方式為"Call By Value",中文翻成傳值呼叫。其機制是將運算式的值複製到堆疊上(也就是說在堆疊上產生新的變數), 然後由被呼叫的函數在堆疊上存取該參數。這種做法的最大優點是,被呼叫者看不到呼叫者定義的區域變數,因此呼叫者不怕其變數被被呼叫者改掉。

void fun(int x, int y) {
     x = 5;
     y = 5;
}
void main() {
    int x = 0;
    int y = 0;
    fun(x, y);
    printf("%d %d\n", x, y);
}

上述的程式執行後會在螢幕上印出兩個0,而不是兩個5。fun(int x, int y)所宣告的x,y和main裡面所宣告的x,y是完全不同的變數。fun只能看到自己的x,y不能看到main裡面的x,y。呼叫fun(x, y)時,這裡的x,y不是變數,而是兩個運算式,這兩個運算式就是LOAD x和LOAD y兩個機器指令。因此Call By Value所傳遞的不是變數的地址,而是該運算式的計算結果。以下範例就更加清楚了:

void fun(int x, int y) {
    x = 5;
    y = 5;
}
void main() {
    int x = 0;
    int y = 0;
    fun(x + 1, y + 1);
    printf("%d %d\n", x, y);
}

fun(x + 1, y + 1)裡運算式x + 1不會有人把它當成變數吧,既然如此fun(x, y)裡的x也一樣不是變數而是運算式。

變數的範圍

討論變數的範圍時,我們必須了解變數的兩項特質

可見範圍(Where): 對C語言來說就是哪些函數可以看到該變數。
存在時間(When): 對C語言來說就是程式執行,或函數呼叫期間。

如果變數定義於函數之外,如

int x;
int main() {
}

則該變數

Where: 程式內所有的函數都可以存取。
When: 整個程式執行期間均存在。

如果變數定義於函數內,如

int main() {
     int x;
}

則該變數

Where: 只有定義該變數的函數(此處為main)可以存取
When: 呼叫該函數時產生,離開該函數就消滅。

由於函數可以遞迴呼叫,因此函數內的變數消滅前可能會呼叫自己而再產生新的變數。此類變數稱為local variable或auto variable,Compiler會把它放在堆疊上。

如果函數可以看到兩個以上同名的變數,則運算式內的變數會以位置最近的為準,所謂位置指的是最接近的{}

double x = 3.14;
int main() {
     int x = 0;
     x = 100; // 此處的x是指上一行的整數x
}

C語言有兩個關鍵字static和extern可用來改變變數的存取範圍

static int x;
int main() {}

Where: 此C檔案內的函數可看到x,其他的原始程式檔都看不到
When: 整個程式執行期間均存在。

int main() {
     static int x;
}

Where: 只有定義該變數的函數(此處為main)可以存取
When: 整個程式執行期間均存在。

extern則表示此變數是在別的檔案內宣告(給空間),此處只是要讓Compiler能夠翻譯相關的運算式,但在此處並不分配空間。這種用法主要在大型專案管理中,有許多程式設計人員撰寫程式,需要用到共同的全域變數,如果每個人定義一次,則Linker會抱怨該變數宣告了一次以上。若都加上static,雖然可以產生執行檔,但實際上大家用的不是同一個變數。正確的做法是:

global.h檔內定義
extern int x;
global.c內定義
int x;
其他人的.c檔內
#include "global.h"

巨集(Macro)

C的前置處理器(Preprocessor)有一個#define命令,可用來取代原始程式內的某些字串:

#define PI 3.14159
main() {
    double r1 = 3.0L, r2 = 5.0L;
    printf("Circle(3) area = %lf", 2 * PI * r1 * r1);
    printf("Circle(5) area = %lf", 2 * PI * r2 * r2);
}

就相當於將程式寫成

main() {
    double r1 = 3.0L, r2 = 5.0L;
    printf("Circle(3) area = %lf", 2 * 3.14159 * r1 * r1);
    printf("Circle(5) area = %lf", 2 * 3.14159 * r2 * r2);
}

define不但可以做簡單的字串取代,還可以加上參數以完成複雜的字串取代工作

#define max(A, B) ((A) > (B) ? (A) : (B))
main() {
     int x, p=3, q=5, r=2, s=7;
     x = max(p+q, r+s);
}

上述程式相當於

main() {
     int x, p=3, q=5, r=2, s=7;
     x = ((p+q) > (r+s) ? (p+q) : (r+s));
}

這種巨集是由preprocessor透過字串取來達成的,和正常的函數呼叫完全不同。在下面的例子中,如果不知道square是巨集的話,就會搞不清楚為何跑出來的結果不正確了

#define square(x) x * x
main() {
    int z = 3;
    printf("%d\n", square(z + 1));
}

印出來是7而不是16喔

遞迴：

意思是重覆呼叫執行自己本身的程式片段，直到符合終止條件為止。撰寫遞迴程式的精神是

要先知道邊際條件(最簡單情形)的解法。
定義函數的參數和傳回值。
如何將大小為n的問題以更小的問題來解答。
在做遞迴呼叫前,別忘了先檢查邊際條件,以免造成無窮呼叫下去的情況。

求1+2+3+...+n

解析

邊際條件是n=1時,總合為1
該函數可定成int sum(int n)
sum(n) = n + sum(n - 1)

int sum(int n) {
    if (n == 1) {
        return 1;
    }
    return n + sum(n - 1);
}

算1*2+2*3+3*4+…+(n-1)*n之和

/* 程式功能:  用遞迴求算1*2+2*3+3*4+…+(n-1)*n之和 */
#include 
int sum(int n);
void main() {
    int n;
    printf("Input the number n: ");
    scanf("%d",&n);
    printf("1*2+2*3+3*4+...+(n-1)*n=%d", sum(n));
}

int sum(int n) {
    if (n == 1) {
        return 0;
    } else {
        return sum(n-1)+n*(n-1);
    }
}

輸入兩數字A, B，利用遞迴求得A的B次方

#include <stdio.h>
power(int a, int b);
void main(void) {
    int x, y;
    printf("Please input two number:");
    scanf("%d %d", &x, &y);
    printf("\n%d^%d = %d", x, y, power(x, y));
}
int power(int a, int b) {
    switch(b) {
    case 0: return 1;
    case 1: return a;
    default: return (a * power(a, b - 1));
    }
}

兩個整數m,n的最大公因數

解析

如果n==0,則最大公因數為m
如果n不等於0,則最大公因數為gcd(m,n)==gcd(n, m%n)

int gcd(int m, int n) {
    if (n == 0) {
        return m;
    }
    return gcd(n, m % n);
}

費式數列

解析

費氏數列的定義為Fn=n, if n<= 1
Fn=Fn-1+Fn-2, if n > 1。
因此遞迴的邊際條件(最簡單情況為)0,1。

int fab(int num) {
    if (num <= 1) {
        return num;
    }
    return fab(num - 1) + fab(num - 2);
}

Ackerman函數

A(m, n)定義為

n+1, if m = 0
A(m-1, 1), if n = 0
A(m-1, A(m, n-1)), otherwise

怎麼寫?

河內塔

在河內塔的問題中,有三根柱子,n個大小不一樣的碟子,一開始時所有n個碟子以大下小上排在某根柱子上。在一次只能移動一個碟子,且不違反大下小上的原則下,如何把這n個碟子全部移到另一根柱子上。

再次回憶遞迴的要點

已知邊際條件(最簡單的情況)如何解
假設某函數已經能解大小為n的問題,也就是要決定此函數的參數和傳回值。
如何利用大小為n的解法,來解更大的問題。

解析

當河內塔的碟子數為0時,問題已解(沒東西好搬了)。
假設三根柱子以int from,to,another來表示,碟子數為n時要這些碟子從from柱子搬到to柱子,解此問題的函數為move(n,from,to,another)。
如何解n+1個碟子的問題呢?
- 我們可以把n個碟子由from搬到another,
- 把最底下的由from搬到to
- 把n個碟子由another搬到to
為甚麼上面的搬法沒問題?當我們搬上面n個碟子時,留在from柱子上的是最大的一個碟子,因此不論我們如何搬動n個碟子,一定不會違反規則,也就是說可以把最底下的當作不存在,好像地板一樣。

/**
 * 河內塔的解法
 */
#include <stdio.h>
void move(int n, int from, int to, int another) {
    if (n > 0) { // 記得遞迴程式要先寫邊際條件才能作遞迴呼叫
        move(n - 1, from, another, to);
        printf("move %d to %d\n", from, to); // 以印出訊息代表搬動的過程
        move(n - 1, another, to, from);
    }
}
int main() {
    int n=0;
    // 一直讀入數字並執行move,直到使用者輸入的數字小於等於0為止
    while (scanf("%d",&n) != EOF && n > 0) {
        move(n,1,2,3);
    }
}