遞歸

博客中代碼已上傳github，點(diǎn)擊此處即可到達(dá)
遞歸指的是在函數(shù)的定義中使用函數(shù)自身的方法。

語(yǔ)法格式如下：

void recursion()
{
   statements;
   ... ... ...
   recursion(); /* 函數(shù)調(diào)用自身 */
   ... ... ...
}
 
int main()
{
   recursion();
}

image

C 語(yǔ)言支持遞歸，即一個(gè)函數(shù)可以調(diào)用其自身。但在使用遞歸時(shí)，程序員需要注意定義一個(gè)從函數(shù)退出的條件，否則會(huì)進(jìn)入死循環(huán)。

遞歸函數(shù)在解決許多數(shù)學(xué)問(wèn)題上起了至關(guān)重要的作用，比如計(jì)算一個(gè)數(shù)的階乘、生成斐波那契數(shù)列，等等。

數(shù)的階乘

下面的實(shí)例使用遞歸函數(shù)計(jì)算一個(gè)給定的數(shù)的階乘：

double factorial(unsigned int a) {
    if (a <= 1) {
        return 1;
    }
    return a * factorial(a - 1);
}

斐波那契數(shù)列

下面的實(shí)例使用遞歸函數(shù)生成一個(gè)給定的數(shù)的斐波那契數(shù)列：

int fabonaci(int i) {
    if (i == 0) {
        return 0;
    } else if (i == 1) {
        return 1;
    } else {
        return fabonaci(i - 1) + fabonaci(i - 2);
    }
}

當(dāng)上面的代碼被編譯和執(zhí)行時(shí)，它會(huì)產(chǎn)生下列結(jié)果：

 double a = factorial(10);
    int b = fabonaci(10);
    printf(" factorial 10 is %f , fabonaci 10 is %d \n", a, b);

 factorial 10 is 3628800.000000 , fabonaci 10 is 55

遞歸是一個(gè)簡(jiǎn)潔的概念，同時(shí)也是一種很有用的手段。但是，使用遞歸是要付出代價(jià)的。與直接的語(yǔ)句(如while循環(huán))相比，遞歸函數(shù)會(huì)耗費(fèi)更多的運(yùn)行時(shí)間，并且要占用大量的?？臻g。遞歸函數(shù)每次調(diào)用自身時(shí)，都需要把它的狀態(tài)存到棧中，以便在它調(diào)用完自身后，程序可以返回到它原來(lái)的狀態(tài)。未經(jīng)精心設(shè)計(jì)的遞歸函數(shù)總是會(huì)帶來(lái)麻煩。

采用遞歸方法來(lái)解決問(wèn)題，必須符合以下三個(gè)條件：

1、可以把要解決的問(wèn)題轉(zhuǎn)化為一個(gè)新問(wèn)題，而這個(gè)新的問(wèn)題的解決方法仍與原來(lái)的解決方法相同，只是所處理的對(duì)象有規(guī)律地遞增或遞減。

說(shuō)明：解決問(wèn)題的方法相同，調(diào)用函數(shù)的參數(shù)每次不同（有規(guī)律的遞增或遞減），如果沒(méi)有規(guī)律也就不能適用遞歸調(diào)用。

2、可以應(yīng)用這個(gè)轉(zhuǎn)化過(guò)程使問(wèn)題得到解決。

說(shuō)明：使用其他的辦法比較麻煩或很難解決，而使用遞歸的方法可以很好地解決問(wèn)題。

3、必定要有一個(gè)明確的結(jié)束遞歸的條件。

說(shuō)明：一定要能夠在適當(dāng)?shù)牡胤浇Y(jié)束遞歸調(diào)用。不然可能導(dǎo)致系統(tǒng)崩潰。

可變參數(shù)

有時(shí)，您可能會(huì)碰到這樣的情況，您希望函數(shù)帶有可變數(shù)量的參數(shù)，而不是預(yù)定義數(shù)量的參數(shù)。C 語(yǔ)言為這種情況提供了一個(gè)解決方案，它允許您定義一個(gè)函數(shù)，能根據(jù)具體的需求接受可變數(shù)量的參數(shù)。下面的實(shí)例演示了這種函數(shù)的定義。

int func(int, ... ) 
{
   .
   .
   .
}
 
int main()
{
   func(2, 2, 3);
   func(3, 2, 3, 4);
}

請(qǐng)注意，函數(shù) func() 最后一個(gè)參數(shù)寫(xiě)成省略號(hào)，即三個(gè)點(diǎn)號(hào)（...），省略號(hào)之前的那個(gè)參數(shù)是 int，代表了要傳遞的可變參數(shù)的總數(shù)。為了使用這個(gè)功能，您需要使用 stdarg.h 頭文件，該文件提供了實(shí)現(xiàn)可變參數(shù)功能的函數(shù)和宏。具體步驟如下：

• 定義一個(gè)函數(shù)，最后一個(gè)參數(shù)為省略號(hào)，省略號(hào)前面可以設(shè)置自定義參數(shù)。
• 在函數(shù)定義中創(chuàng)建一個(gè) va_list 類(lèi)型變量，該類(lèi)型是在 stdarg.h 頭文件中定義的。
• 使用 int 參數(shù)和 va_start 宏來(lái)初始化 va_list 變量為一個(gè)參數(shù)列表。宏 va_start 是在 stdarg.h 頭文件中定義的。
• 使用 va_arg 宏和 va_list 變量來(lái)訪問(wèn)參數(shù)列表中的每個(gè)項(xiàng)。
• 使用宏 va_end 來(lái)清理賦予 va_list 變量的內(nèi)存。

現(xiàn)在讓我們按照上面的步驟，來(lái)編寫(xiě)一個(gè)帶有可變數(shù)量參數(shù)的函數(shù)，并返回它們的平均值：

double average_nums(int num,...){
    va_list list;
    double sum=0;

    /* 為 num 個(gè)參數(shù)初始化 valist */
    va_start(list,num);


    /* 訪問(wèn)所有賦給 valist 的參數(shù) */
    /* 訪問(wèn)所有賦給 valist 的參數(shù) */
    for (int i = 0; i < num; i++)
    {
        sum += va_arg(list, int);
    }
    /* 清理為 valist 保留的內(nèi)存 */
    va_end(list);

    return sum/num;
}

double c = average_nums(5, 1, 600, 5, 7, 9);
    printf(" average_nums 5 is %f ",c);

 average_nums 5 is 124.400000

C 函數(shù)要在程序中用到以下這些宏:

void va_start( va_list arg_ptr, prev_param ); 
type va_arg( va_list arg_ptr, type ); 
void va_end( va_list arg_ptr );

va_list: 用來(lái)保存宏va_start、va_arg和va_end所需信息的一種類(lèi)型。為了訪問(wèn)變長(zhǎng)參數(shù)列表中的參數(shù)，必須聲明 va_list 類(lèi)型的一個(gè)對(duì)象，定義： typedef char * va_list;

va_start: 訪問(wèn)變長(zhǎng)參數(shù)列表中的參數(shù)之前使用的宏，它初始化用 va_list 聲明的對(duì)象，初始化結(jié)果供宏 va_arg 和 va_end 使用；

va_arg: 展開(kāi)成一個(gè)表達(dá)式的宏，該表達(dá)式具有變長(zhǎng)參數(shù)列表中下一個(gè)參數(shù)的值和類(lèi)型。每次調(diào)用 va_arg 都會(huì)修改用 va_list 聲明的對(duì)象，從而使該對(duì)象指向參數(shù)列表中的下一個(gè)參數(shù)；

va_end: 該宏使程序能夠從變長(zhǎng)參數(shù)列表用宏 va_start 引用的函數(shù)中正常返回。

va 在這里是 variable-argument(可變參數(shù)) 的意思。

這些宏定義在 stdarg.h 中，所以用到可變參數(shù)的程序應(yīng)該包含這個(gè)頭文件。

下面我們寫(xiě)一個(gè)簡(jiǎn)單的可變參數(shù)的函數(shù)，該函數(shù)至少有一個(gè)整數(shù)參數(shù)，第二個(gè)參數(shù)也是整數(shù)，是可選的。函數(shù)只是打印這兩個(gè)參數(shù)的值。

int changeable_varity(char *msg, ...) {

    va_list argp;                    /* 定義保存函數(shù)參數(shù)的結(jié)構(gòu) */
    int argno = 0;                    /* 紀(jì)錄參數(shù)個(gè)數(shù) */
    char *para;                        /* 存放取出的字符串參數(shù) */
    va_start( argp, msg );          /* argp指向傳入的第一個(gè)可選參數(shù)，      msg是最后一個(gè)確定的參數(shù) */

    while (1)
    {
        para = va_arg( argp, char *);                 /*      取出當(dāng)前的參數(shù)，類(lèi)型為char *. */
        if ( strcmp( para, "/0") == 0 )
            /* 采用空串指示參數(shù)輸入結(jié)束 */
            break;
        printf("Parameter #%d is: %s\n", argno, para);
        argno++;
    }
    va_end( argp );                                   /* 將argp置為NULL */
    return 0;
}

changeable_varity("FAKER","what", "are", "you", "nong", "sha", "lei","/0");

Parameter #0 is: what
Parameter #1 is: are
Parameter #2 is: you
Parameter #3 is: nong
Parameter #4 is: sha
Parameter #5 is: lei

從這個(gè)函數(shù)的實(shí)現(xiàn)可以看到,我們使用可變參數(shù)應(yīng)該有以下步驟:

• 1)首先在函數(shù)里定義一個(gè) va_list 型的變量,這里是 arg_ptr，這個(gè)變量是指向參數(shù)的指針。
• 2)然后用 va_start 宏初始化變量 arg_ptr，這個(gè)宏的第二個(gè)參數(shù)是第一個(gè)可變參數(shù)的前一個(gè)參數(shù)，是一個(gè)固定的參數(shù)。
• 3)然后用 va_arg 返回可變的參數(shù)，并賦值給整數(shù) j。va_arg 的第二個(gè)參數(shù)是你要返回的參數(shù)的類(lèi)型，這里是int型。
• 4)最后用 va_end 宏結(jié)束可變參數(shù)的獲取。然后你就可以在函數(shù)里使用第二個(gè)參數(shù)了。如果函數(shù)有多個(gè)可變參數(shù)的，依次調(diào)用 va_arg 獲取各個(gè)參數(shù)。

內(nèi)存管理

本章將講解 C 中的動(dòng)態(tài)內(nèi)存管理。C 語(yǔ)言為內(nèi)存的分配和管理提供了幾個(gè)函數(shù)。這些函數(shù)可以在 <stdlib.h> 頭文件中找到。

注意：void * 類(lèi)型表示未確定類(lèi)型的指針。C、C++ 規(guī)定 void * 類(lèi)型可以通過(guò)類(lèi)型轉(zhuǎn)換強(qiáng)制轉(zhuǎn)換為任何其它類(lèi)型的指針。

動(dòng)態(tài)分配內(nèi)存

編程時(shí)，如果您預(yù)先知道數(shù)組的大小，那么定義數(shù)組時(shí)就比較容易。例如，一個(gè)存儲(chǔ)人名的數(shù)組，它最多容納 100 個(gè)字符，所以您可以定義數(shù)組，如下所示：

char name[100];

但是，如果您預(yù)先不知道需要存儲(chǔ)的文本長(zhǎng)度，例如您向存儲(chǔ)有關(guān)一個(gè)主題的詳細(xì)描述。在這里，我們需要定義一個(gè)指針，該指針指向未定義所需內(nèi)存大小的字符，后續(xù)再根據(jù)需求來(lái)分配內(nèi)存，如下所示：

void dynamic_allocation_memory() {
    char name[100];
    char *description;

    strcpy(name, "Tony Anndy");
    // description = (char *) _malloc(200 * sizeof(char));
    /* 動(dòng)態(tài)分配內(nèi)存 */
    description = (char *) malloc(200 * sizeof(char));

    if (description == NULL) {
        fprintf(stderr, "Error - unable to allocate required memory\n");
    } else {
        strcpy(description, "Tony Anndy is DPS gay in class 10th");
    }
    printf("Name = %s\n", name);
    printf("Description: %s\n", description);
};

當(dāng)上面的代碼被編譯和執(zhí)行時(shí)，它會(huì)產(chǎn)生下列結(jié)果：

Name = Tony Anndy
Description: Tony Anndy is DPS gay in class 10th

上面的程序也可以使用 calloc() 來(lái)編寫(xiě)，只需要把 malloc 替換為 calloc 即可，如下所示：

calloc(200, sizeof(char));

當(dāng)動(dòng)態(tài)分配內(nèi)存時(shí)，您有完全控制權(quán)，可以傳遞任何大小的值。而那些預(yù)先定義了大小的數(shù)組，一旦定義則無(wú)法改變大小。

重新調(diào)整內(nèi)存的大小和釋放內(nèi)存

當(dāng)程序退出時(shí)，操作系統(tǒng)會(huì)自動(dòng)釋放所有分配給程序的內(nèi)存，但是，建議您在不需要內(nèi)存時(shí)，都應(yīng)該調(diào)用函數(shù) free() 來(lái)釋放內(nèi)存。

或者，您可以通過(guò)調(diào)用函數(shù) realloc() 來(lái)增加或減少已分配的內(nèi)存塊的大小。讓我們使用 realloc() 和 free() 函數(shù)，再次查看上面的實(shí)例：

void dynamic_allocation_memory() {
    char name[100];
    char *description;

    strcpy(name, "Tony Anndy");
    // description = (char *) _malloc(200 * sizeof(char));
    /* 動(dòng)態(tài)分配內(nèi)存 */
    description = (char *) malloc(80 * sizeof(char));

    if (description == NULL) {
        fprintf(stderr, "Error - unable to allocate required memory\n");
    } else {
        strcpy(description, "Tony Anndy is DPS gay in class 10th ");
    }

    /* 假設(shè)您想要存儲(chǔ)更大的描述信息 */
    description = realloc(description, 100 * sizeof(char));
    if (description == NULL) {
        fprintf(stderr, "Error - unable to allocate required memory\n");
    } else {
        strcat(description, "She is in class 10th");
    }

    printf("Name = %s\n", name);
    printf("Description: %s\n", description);
};

對(duì)于 void 指針，GNU 認(rèn)為 void * 和 char * 一樣，所以以下寫(xiě)法是正確的:

description = malloc( 200 * sizeof(char) );

但按照 ANSI(American National Standards Institute) 標(biāo)準(zhǔn)，需要對(duì) void 指針進(jìn)行強(qiáng)制轉(zhuǎn)換，如下:

description = (char *)malloc( 200 * sizeof(char) );

同時(shí)，按照 ANSI(American National Standards Institute) 標(biāo)準(zhǔn)，不能對(duì) void 指針進(jìn)行算法操作:

void * pvoid;
pvoid++; //ANSI：錯(cuò)誤
pvoid += 1; //ANSI：錯(cuò)誤
// ANSI標(biāo)準(zhǔn)之所以這樣認(rèn)定，是因?yàn)樗鼒?jiān)持：進(jìn)行算法操作的指針必須是確定知道其指向數(shù)據(jù)類(lèi)型大小的。

int *pint;
pint++; //ANSI：正確

代碼已上傳github，點(diǎn)擊此處即可到達(dá)