【 聲明：版權所有，歡迎轉載，請勿用於商業用途。 聯系信箱：feixiaoxing @163.com】
看過我前面博客的朋友都清楚，函數調用主要依靠ebp和esp的堆棧互動來實現的。那麼遞歸呢，最主要的特色就是函數自己調用自己。如果一個函數調用的是自己本身，那麼這個函數就是遞歸函數。
我們可以看一下普通函數的調用怎麼樣的。試想如果函數A調用了函數B，函數B又調用了函數C，那麼在堆棧中的數據是怎麼保存的呢？
view plaincopy to clipboardprint?函數A ^
函數B | (地址遞減)
函數C |
函數A ^
函數B | (地址遞減)
函數C | 如果是遞歸函數呢，舉一個簡單的遞歸函數為例：
view plaincopy to clipboardprint?int iterate(int value)
{
if(value == 1)
return 1;
return value + iterate(value -1);
}
int iterate(int value)
{
if(value == 1)
return 1;
return value + iterate(value -1);
} 下面我們使用一個函數進行調用，看看會發生什麼情況？
view plaincopy to clipboardprint?void process()
{
int value = iterate(6);
}
void process()
{
int value = iterate(6);
} 看看此時內存堆棧是什麼樣的？
view plaincopy to clipboardprint?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()
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()
大家也看到了上面的代碼，遞歸函數和普通的函數也沒有什麼差別。除了自己調用本身之外，他就是一個普通的函數。那麼這個函數遞歸到什麼時候返回呢？這就是遞歸函數的關鍵了。我們看到iterate函數到1就停止了，所以上面的堆棧在（value == 1）即return。所以一個遞歸函數最關鍵的部分就是兩點：（1）遞歸策略；（2）函數出口。
看到這裡，大家可能感到遞歸函數不過如此，事實上也是這樣。但是，還有一點大家需要牢記在心，遞歸的深度是我們必須考慮的一個問題。只有遞歸深度在一個可控的范圍內，那麼整個遞歸過程都是可控的。那什麼時候不可控呢？那就是遞歸深度超過了一定的數字？這個數字和具體的線程堆棧長度有關？等到堆棧溢出了，那麼獲得的數據已經失去了真實性，所以也就沒有意義了。
我們把上面的問題推廣一下，如何用自己定義的堆棧模擬上面的遞歸調用呢？這樣既能滿足遞歸的屬性，又能確保函數深度可控。
大家可以先寫一下自己的方案，下面只是我個人的一個思路。
view plaincopy to clipboardprint?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;
}
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;
}
【預告： 下面一篇博客介紹算法和內存】
