其實(shí)編程的朋友知道，不管學(xué)什么語言，循環(huán)和遞歸是兩個(gè)必須學(xué)習(xí)的內(nèi)容。當(dāng)然，如果循環(huán)還好理解一點(diǎn)，那么遞歸卻沒有那么簡單。我們曾經(jīng)對遞歸諱莫如深，但是我想告訴大家的是，遞歸其實(shí)沒有那么可怕。所謂的遞歸就是函數(shù)自己調(diào)用自己而已，循環(huán)本質(zhì)上也是一種遞歸。

1）求和遞歸函數(shù)

我們可以舉一個(gè)循環(huán)的例子，前面我們說過，如果編寫一個(gè)1到n的求和函數(shù)怎么寫呢，你可能會(huì)這么寫：

int calculate(int m)
{
    int count = 0;
    if(m <0)
        return -1;

    for(int index = 0; index <= m; index++)
        count += index;

    return count;
}

上面只是一個(gè)示范。下面我們看看如果是遞歸應(yīng)該怎么寫呢？

int calculate(int m)
{
    if(m == 0)
        return 0;
    else
        return calculate(m -1) + m;
}

大家看著兩段代碼有什么不同？

（1）第一段代碼從0，開始計(jì)算，從0到m逐步計(jì)算；第二段代碼是從10開始計(jì)算，逐步到0之后這回，這樣同樣可以達(dá)到計(jì)算的效果

（2）第一段代碼不需要重復(fù)的壓棧操作，第二段需要重復(fù)的函數(shù)操作，當(dāng)然這也是遞歸的本質(zhì)

（3）第一段代碼比較長，第二段代碼較短

2）查找遞歸函數(shù)

大家可能說，這些代碼有些特殊。如果是查找類的函數(shù)，有沒有可能修改成遞歸函數(shù)呢？

int find(int array[], int length, int value)
{
    int index = 0;
    if(NULL == array || 0 == length)
        return -1;

    for(; index < length; index++)
    {
        if(value == array[index])
            return index;
    }

    return -1;
}

大家可能說，這樣的代碼可能修改成這樣的代碼：

int _find(int index, int array[], int length, int value)
{
    if(index == length)
        return -1;

    if(value == array[index])
        return index;

    return _find(index + 1,  array, length, value);
}

int find(int array[], int length, int value)
{
    if(NULL == array || length == 0)
        return -1;

    return _find(0, array, length, value);
}

3） 指針變量遍歷

結(jié)構(gòu)指針是我們喜歡的遍歷結(jié)構(gòu)，試想如果有下面定義的數(shù)據(jù)結(jié)構(gòu)：

typedef struct _NODE
{
    int data;
    struct _NODE* next;
}NODE;

那么，此時(shí)我們需要對一個(gè)節(jié)點(diǎn)鏈接中的所有數(shù)據(jù)進(jìn)行打印，應(yīng)該怎么辦呢？大家可以自己先想想，然后看看我們寫的代碼對不對。

void print(const NODE* pNode)
{
    if(NULL == pNode)
        return;

    while(pNode){
        printf("%dn", pNode->data);
        pNode = pNode->next;
    }
}

那么此時(shí)如果改成遞歸，那就更簡單了：

void print(const NODE* pNode)
{
    if(NULL == pNode)
        return;
    else
        printf("%dn", pNode->data);

    print(pNode->next);
}

其實(shí)，寫這么多，就是想和大家分享一下我個(gè)人的觀點(diǎn)：循環(huán)是一種特殊的遞歸，只有遞歸和堆棧是等價(jià)的。所有的遞歸代碼都可以寫成堆棧的形式，下面的一片博客我們就討論一下堆棧和遞歸的關(guān)系。要想寫好，必須熟練掌握堆棧。