一步一步寫算法（之循環和遞歸）

【 聲明：版權所有，歡迎轉載，請勿用于商業用途。  聯系信箱：feixiaoxing @163.com】

    其實程式設計的朋友知道，不管學什麼語言，循環和遞歸是兩個必須學習的内容。當然，如果循環還好了解一點，那麼遞歸卻沒有那麼簡單。我們曾經對遞歸諱莫如深，但是我想告訴大家的是，遞歸其實沒有那麼可怕。所謂的遞歸就是函數自己調用自己而已，循環本質上也是一種遞歸。

    1）求和遞歸函數

    我們可以舉一個循環的例子，前面我們說過，如果編寫一個1到n的求和函數怎麼寫呢，你可能會這麼寫：

    上面隻是一個示範。下面我們看看如果是遞歸應該怎麼寫呢？

    大家看着兩段代碼有什麼不同？

    （1）第一段代碼從0，開始計算，從0到m逐漸計算；第二段代碼是從10開始計算，逐漸到0之後這回，這樣同樣可以達到計算的效果

    （2）第一段代碼不需要重複的壓棧操作，第二段需要重複的函數操作，當然這也是遞歸的本質

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

    2）查找遞歸函數

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

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

    3） 指針變量周遊

    結構指針是我們喜歡的周遊結構，試想如果有下面定義的資料結構：

    那麼，此時我們需要對一個節點連結中的所有資料進行列印，應該怎麼辦呢？大家可以自己先想想，然後看看我們寫的代碼對不對。

    那麼此時如果改成遞歸，那就更簡單了：

    其實，寫這麼多，就是想和大家分享一下我個人的觀點：循環是一種特殊的遞歸，隻有遞歸和堆棧是等價的。所有的遞歸代碼都可以寫成堆棧的形式，下面的一片部落格我們就讨論一下堆棧和遞歸的關系。要想寫好，必須熟練掌握堆棧。

【預告： 下面一片部落格介紹堆棧和遞歸】