遞歸 (電腦科學)

遞歸（粵拼：dai6 gwai1；英文：recursion）喺程式編寫上，如果係講緊子程式嘅定義，狹義上係指子程式嘅定義會直接用到自己，廣義上就指子程式會直接或者間接用到自己；如果講子程式嘅執行，指嘅係指子程式會直接或者間接啟動自己。遞歸可以用來將一條問題分做條問題「細啲嘅版本」噉嚟解。

狹義上子程式嘅遞歸，原則上同邏輯上講嗰種遞歸上係同一樣嘢，都係 ｢用自己定義自己｣，但係子程式嘅啟動牽涉有限資源同副作用等等；廣義嘅遞歸，或者執行嘅時候講嘅遞歸，都可以視為狹義嘅遞歸喺特定語境之下嘅引伸義。

喺程式語言嘅理論上，遞歸有兩種特別情形：如果喺實際執行嘅時候，一個子程式嘅啟動（activation）最多只會再啟動自己一次，呢種叫 linear recursion（線性遞歸）。如果一個子程式一係唔啟動自己，一係就喺輸出（return）嘅時候先啟動自己，呢種叫尾遞歸（tail recursion）；喺翻譯嘅時候，尾遞歸係可以有方法令佢實際上變成唔涉及遞歸嘅其他嘅流程控制。

概論

睇埋：控制流程

基本諗頭

内文：子程式同遞歸

遞歸最重要嘅特徵，係指一個子程式會「用到自己」或者「𠹭call自己」。呢種做法可以當係分治演算法嘅一類，將一個大嘅問題「揼散」做若干個細嘅問題。舉例說明，想像依家要教電腦計階乘嘅數，可以想像以下嘅虛擬碼：

呢個子程式叫 factorial(x)

如果 x == 0：

Output 係 1

否則：

Output 係 x 乘以 factorial(x-1)

——factorial 呢個子程式，會「用返自己」。假如 input x 數值係 5，行呢個程式就會好似噉：

factorial(x) 行嗰陣嘅情況

1. 個程式行 factorial(x-1)，呢個 factorial 以 4 做 input；
2. 個程式行 factorial(x-1)，呢個 factorial 以 3 做 input；
3. 個程式行 factorial(x-1)，呢個 factorial 以 2 做 input；
4. 個程式行 factorial(x-1)，呢個 factorial 以 1 做 input；
5. 個程式行 factorial(x-1)，呢個 factorial 以 0 做 input；
6. 因為 x 數值去到 0，個子程式出 1；
7. return x * factorial(x-1)，factorial(0) 出 1，1 * 1 出 1；
8. return x * factorial(x-1)，factorial(1) 出 1，2 * 1 出 2；
9. return x * factorial(x-1)，factorial(2) 出 2，3 * 2 出 6；
10. return x * factorial(x-1)，factorial(3) 出 6，4 * 6 出 24；
11. return x * factorial(x-1)，factorial(4) 出 24，5 * 24 出 120；
12. 最後成個程式出 120 做答案。

如是者，個程式就計到階乘 $5!=5\times 4\times 3\times 2\times 1=120$。

兩大部份

睇埋：無限迴圈

一個用咗遞歸嘅子程式，有兩大組成部份：基本個案同遞歸個案：

• 基本個案會「即刻畀 output」，唔會引致任何進一步嘅遞歸，電腦一𠹭佢，就會得到 output。好似係計階乘嗰個例子噉，佢個基本個案就係 如果 x == 0：output 係 1 嗰一截。用親遞歸嘅子程式都梗要有個基本個案，唔係嘅話個子程式就會進入無限迴圈。
• 遞歸個案會有進一步遞歸，但係每一次遞歸個問題都會「細咗」或者「簡單咗」，而且會愈嚟愈接近基本個案。喺計階乘嘅例子裡便，佢個遞歸個案係 否則：output 係 x 乘以 factorial(x-1) 嗰截——呢段嘢每行一次，個問題都會愈嚟愈接近基本個案。

有啲人會將上述過程想像成「一個堆堆裝住未解嘅遞歸個案，遞歸個案一個個噉堆，堆到去到基本個案，再一個個噉解咗佢」。

堆疊嘅圖解；堆疊有一舊舊數據，處理起上嚟係「後入先出」（LIFO）嘅，喺呢方面遞歸好相似，個子程式一路行，行到去基本個案度，然後越接近基本個案嘅會「解決咗先」。 堆疊嘅圖解；堆疊有一舊舊數據，處理起上嚟係「後入先出」（LIFO）嘅，喺呢方面遞歸好相似，個子程式一路行，行到去基本個案度，然後越接近基本個案嘅會「解決咗先」。

遞歸種類

「遞歸嘅威力在於佢能夠用有限嘅陳述式，定義無限咁多件物件。同一道理，有限嘅遞歸程式可以描述數量無限嘅運算，而且就算個程式冇講明要重複都得。」

——尼克勞斯·維爾特

單一定多重

費氏數列嘅圖像化：圖中每個正方形嘅邊長係費氏數列其中一個數。

遞歸可以分做單一同多重兩種。呢個分類係講緊個子程式會𠹭call佢自己𠹭幾多次，單一遞歸比較簡單，個子程式嘅定義只會𠹭自己一次，而多重遞歸就比較複雜，個子程式嘅定義會𠹭自己超過一次。

例如費氏數列就可以用多重遞歸嚟計。費氏數列係一個好出名嘅數列，頭兩個數係 0 同 1，跟住落嚟嘅數就係之前兩個數加埋嘅和，即係：

$F_{0}=0,F_{1}=1$，而且

$F_{n+2}=F_{n}+F_{n+1}$

想像以下呢段演算法嘅虛擬碼，用家是但入一個正整數 n，段演算法會計出費氏數列入便第 n 個數係乜：

定義子程式 fibGen(self, n)：

如果 n <= 1：

畀 n 做答案

否則

畀 fibGen(n-1) + fibGen(n-2)

好多編程工作者都主張，多重遞歸呢家嘢可免則免。一個程式用咗多重遞歸，好易出現運算複雜度過高嘅問題。例如睇返上面嗰段計費氏數列嘅演算法噉，個子程式每行一次，都會𠹭自己兩次，然後嗰兩個𠹭就會各自產生多兩個𠹭變成四個𠹭——兩重遞歸嘅運算複雜度會傾向同 $2^{n}$ 成正比。而如果段演算法有三重遞歸，個子程式每行一次，就會𠹭自己三次，而三個𠹭都會各自產生多三個𠹭變成九個𠹭——三重遞歸嘅運算複雜度會傾向同 $3^{n}$ 成正比。

直接定間接

内文：相互遞歸

尾遞歸

内文：尾遞歸

理論分析

睇埋：分治演算法

出名應用

睇埋：樹狀數據同碎形

喺編程上，遞歸可以用嚟解決一啲可以揼散做一大柞細問題嘅問題，而且當中每一個細問題都屬同一個類型。

對比疊代

睇埋：疊代

睇埋

• 自指
• 鏈結串列
• 最大最小化

文獻

• Dijkstra, Edsger W. (1960). "Recursive Programming". Numerische Mathematik. 2 (1): 312–318. doi:10.1007/BF01386232.

參考

註釋：

篇文用咗嘅行話詞彙，英文名如下：

篇文引用咗以下呢啲文獻同網頁：

拎

• 遞歸簡介 — 數據結構同演算法教學，GeeksForGeeks