一些電腦編程語言允許一個模組或函數來調用自身。這種技術被稱為遞歸。在遞歸函數α直接調用自己或調用函數β，反過來調用原函數α。該函數α被稱為遞歸函數。
特性
遞歸函數可以無限執行就類似一個迴圈。為了避免遞歸函數的無窮運行，一個遞歸函數必須具備有兩個屬性 -
-
基本準則 − 必須有至少一個基本的標準或條件，例如，當滿足此條件時函數停止遞歸調用自身。
-
由淺入深 − 遞歸調用應該在那個遞歸調用作出每次涉及靠近基標準這樣的方式前進。
實現
許多編程語言通過堆疊的方式實現遞歸。一般來說，當一個函數（調用者）調用另一個函數（被調用者）或本身作為被調用， 調用者傳送函數執行控制權被調用。
這意味著，調用方函數具有暫停其執行並在稍後繼續時從被調用函數的執行控制返回。在這裏，調用函數需要從執行的角度入手正是它把自己擱置。它也需要完全相同的數據值執行。為此，活動記錄（或堆疊幀）可以創建調用函數。
此活動記錄保留局部變數的資訊，形式參數，返回地址並傳遞給調用函數的所有資訊。
遞歸分析
有人可能會認為，作為同樣的任務可以反復地來完成，為什麼使用遞歸？第一個原因是遞歸使得程式更具可讀性，並因為今天的提升 CPU 系統中，遞歸比迭代更加高效。
時間複雜度
如果是迭代，我們採取迭代次數來計算的時間複雜度。同樣，在遞歸的情況下，假設一切都不變，我們試著找出遞歸調用的次數。 調用一個函數是 Ο(1), 因此（n）數量是遞歸調用作出遞歸函數的時間 Ο(n)。
空間複雜度
空間複雜度是算作所需要的執行模組的額外空間量。如遇迭代，編譯器幾乎不要求任何額外的空間。 編譯器不斷更新並反復使用的變數值。 但如遇到遞歸，系統需要的遞歸調用作出每次存儲啟動記錄。因此可以認為，空間遞歸函數的複雜性可能比用迭代的函數去更高。