看過我前面博客的朋友都清楚，函數(shù)調用主要依靠ebp和esp的堆棧互動來實現(xiàn)的。那么遞歸呢，最主要的特色就是函數(shù)自己調用自己。如果一個函數(shù)調用的是自己本身，那么這個函數(shù)就是遞歸函數(shù)。

我們可以看一下普通函數(shù)的調用怎么樣的。試想如果函數(shù)A調用了函數(shù)B，函數(shù)B又調用了函數(shù)C，那么在堆棧中的數(shù)據(jù)是怎么保存的呢？

函數(shù)A    ^
函數(shù)B    |    (地址遞減)
函數(shù)C    |

如果是遞歸函數(shù)呢，舉一個簡單的遞歸函數(shù)為例：

int iterate(int value)
{
    if(value == 1)
        return 1;
    return value + iterate(value -1);
}

下面我們使用一個函數(shù)進行調用，看看會發(fā)生什么情況？

void process()
{
    int value = iterate(6);
}

看看此時內存堆棧是什么樣的？

iterate(int 1) line 96
iterate(int 2) line 97 + 12 bytes
iterate(int 3) line 97 + 12 bytes
iterate(int 4) line 97 + 12 bytes
iterate(int 5) line 97 + 12 bytes
iterate(int 6) line 97 + 12 bytes
process() line 102 + 7 bytes
main() line 108
mainCRTStartup() line 206 + 25 bytes
KERNEL32! 7c817067()

大家也看到了上面的代碼，遞歸函數(shù)和普通的函數(shù)也沒有什么差別。除了自己調用本身之外，他就是一個普通的函數(shù)。那么這個函數(shù)遞歸到什么時候返回呢？這就是遞歸函數(shù)的關鍵了。我們看到iterate函數(shù)到1就停止了，所以上面的堆棧在（value == 1）即return。所以一個遞歸函數(shù)最關鍵的部分就是兩點：（1）遞歸策略；（2）函數(shù)出口。

看到這里，大家可能感到遞歸函數(shù)不過如此，事實上也是這樣。但是，還有一點大家需要牢記在心，遞歸的深度是我們必須考慮的一個問題。只有遞歸深度在一個可控的范圍內，那么整個遞歸過程都是可控的。那什么時候不可控呢？那就是遞歸深度超過了一定的數(shù)字？這個數(shù)字和具體的線程堆棧長度有關？等到堆棧溢出了，那么獲得的數(shù)據(jù)已經(jīng)失去了真實性，所以也就沒有意義了。

我們把上面的問題推廣一下，如何用自己定義的堆棧模擬上面的遞歸調用呢？這樣既能滿足遞歸的屬性，又能確保函數(shù)深度可控。

大家可以先寫一下自己的方案，下面只是我個人的一個思路。

int iterate(int value)
{
    int count = 0;
    int number  =0;

    push(value);
    while(-1 != (number = pop()))
    {
        if(1 != number)
            push(number -1);
        count += number;
    }

    return count;
}