遞歸基礎知識

一些計算機編程語言允許一個模塊或函數來調用自身。這種技術被稱爲遞歸。在遞歸函數α直接調用自己或調用函數β，反過來調用原函數α。該函數α被稱爲遞歸函數。

特性

遞歸函數可以無限執行就類似一個循環。爲了避免遞歸函數的無窮運行，一個遞歸函數必須具備有兩個屬性 -

• 基本準則 − 必須有至少一個基本的標準或條件，例如，當滿足此條件時函數停止遞歸調用自身。

• 由淺入深 − 遞歸調用應該在那個遞歸調用作出每次涉及靠近基標準這樣的方式前進。

實現

許多編程語言通過堆棧的方式實現遞歸。一般來說，當一個函數（調用者）調用另一個函數（被調用者）或本身作爲被調用， 調用者傳送函數執行控制權被調用。

這意味着，調用方函數具有暫停其執行並在稍後繼續時從被調用函數的執行控制返回。在這裏，調用函數需要從執行的角度入手正是它把自己擱置。它也需要完全相同的數據值執行。爲此，活動記錄（或堆棧幀）可以創建調用函數。

此活動記錄保留局部變量的信息，形式參數，返回地址並傳遞給調用函數的所有信息。

遞歸分析

有人可能會認爲，作爲同樣的任務可以反覆地來完成，爲什麼使用遞歸？第一個原因是遞歸使得程序更具可讀性，並因爲今天的提升 CPU 系統中，遞歸比迭代更加高效。

時間複雜度

如果是迭代，我們採取迭代次數來計算的時間複雜度。同樣，在遞歸的情況下，假設一切都不變，我們試着找出遞歸調用的次數。 調用一個函數是 Ο(1), 因此（n）數量是遞歸調用作出遞歸函數的時間 Ο(n)。

空間複雜度

空間複雜度是算作所需要的執行模塊的額外空間量。如遇迭代，編譯器幾乎不要求任何額外的空間。 編譯器不斷更新並反覆使用的變量值。 但如遇到遞歸，系統需要的遞歸調用作出每次存儲激活記錄。因此可以認爲，空間遞歸函數的複雜性可能比用迭代的函數去更高。