Java 資料結構 - 遞迴

某些計算機程式語言允許模組或函式呼叫自身。這種技術稱為遞迴。在遞迴中，函式α要麼直接呼叫自身，要麼呼叫一個函式β，而該函式β又反過來呼叫原始函式α。函式α稱為遞迴函式。

int sampleMethod(int value) {
   if(value < 1) {
      return;
   }
   sampleMethod(value - 1);
   System.out.println(value);   
}

屬性

遞迴函式可能會像迴圈一樣無限執行。為了避免遞迴函式無限執行，遞迴函式必須具有以下兩個屬性：

• 基本條件 - 必須至少有一個基本條件，當滿足此條件時，函式停止遞迴呼叫自身。

• 漸進方法 - 遞迴呼叫應該以這樣的方式進行，即每次進行遞迴呼叫時，它都更接近基本條件。

實現

許多程式語言透過堆疊來實現遞迴。通常，每當一個函式（呼叫者）呼叫另一個函式（被呼叫者）或自身作為被呼叫者時，呼叫者函式將執行控制轉移給被呼叫者。此轉移過程可能還涉及將一些資料從呼叫者傳遞給被呼叫者。

這意味著，呼叫者函式必須暫時暫停其執行，並在執行控制從被呼叫者函式返回時恢復。在此，呼叫者函式需要從其暫停執行的點開始精確執行。它還需要它正在處理的完全相同的資料值。為此，將為呼叫者函式建立一個啟用記錄（或堆疊幀）。

此啟用記錄儲存有關區域性變數、形式引數、返回地址以及傳遞給呼叫者函式的所有資訊。

遞迴分析

有人可能會質疑為什麼要使用遞迴，因為可以使用迭代來完成相同的任務。第一個原因是，遞迴使程式更易於閱讀，並且由於最新的增強型 CPU 系統，遞迴比迭代更高效。

時間複雜度

在迭代的情況下，我們採用迭代次數來計算時間複雜度。同樣，在遞迴的情況下，假設所有內容都是恆定的，我們試圖找出進行遞迴呼叫的次數。對函式的呼叫為 Ο(1)，因此進行 (n) 次遞迴呼叫使得遞迴函式為 Ο(n)。

空間複雜度

空間複雜度計算的是模組執行需要多少額外空間。在迭代的情況下，編譯器幾乎不需要任何額外空間。編譯器不斷更新迭代中使用的變數的值。但在遞迴的情況下，系統需要在每次進行遞迴呼叫時儲存啟用記錄。因此，認為遞迴函式的空間複雜度可能高於使用迭代的函式。