遞歸 (電腦科學)

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

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

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

## 基本諗頭

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

:**呢個子程式叫** factorial(x)
::如果 x == 0：
:::Output 係 1
::否則：
:::Output 係 x 乘以 factorial(x-1)

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

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

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

### 兩大部份

一個用咗遞歸嘅子程式，有兩大組成部份：基本個案同遞歸個案。
***基本個案**會「即刻畀 output」，唔會引致任何進一步嘅遞歸，電腦一𠹭佢，就會得到 output。好似係計階乘嗰個例子噉，佢個基本個案就係 `如果 x == 0：output 係 1` 嗰一截。用親遞歸嘅子程式都梗要有個基本個案，唔係嘅話個子程式就會進入無限迴圈。
***遞歸個案**會有進一步遞歸，但係每一次遞歸個問題都會「細咗」或者「簡單咗」，而且會愈嚟愈接近基本個案。喺計階乘嘅例子裡便，佢個遞歸個案係 `否則：output 係 x 乘以 factorial(x-1)` 嗰截——呢段嘢每行一次，個問題都會愈嚟愈接近基本個案。
有啲人會將上述過程想像成「一個堆堆裝住未解嘅遞歸個案，遞歸個案一個個噉堆，堆到去到基本個案，再一個個噉解咗佢」。

## 遞歸種類

### 單一定多重

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

例如費氏數列就可以用多重遞歸嚟計。費氏數列係一個好出名嘅數列，頭兩個數係 0 同 1，跟住落嚟嘅數就係之前兩個數加埋嘅和，假設 *n* 係整數，數學上就可以噉定義：
:
\begin{cases}
F_0=0 \\
F_1=1 \\
F_{n} = F_{n-2} + F_{n-1} \qquad\forall n>1
\end{cases}
將數學定義直接譯做演算法，就會得出類似下面嘅虛擬碼：

:**子程式** *fib* ( *n* )：
::**如果** *n* ≤ 1：
:::答案係 *n*
::**否則**
:::答案係 *fib* (*n* - 2) + *fib* (*n* - 1)

最後一行有 *fib* (*n* - 2) 同 *fib* (*n* - 1) 兩個，兩個呼叫都會執行，所以噉做法係多重遞歸。

一個程式用咗多重遞歸，好易會出現運算複雜度過高嘅問題。例如上面嗰段演算法，個子程式每行一次，都會叫自己兩次，然後嗰兩個呼叫就會各自產生多兩個呼叫變成四個呼叫——兩重遞歸嘅運算複雜度會傾向係 <math>O(2^n)</math>（即係同 2^n 成正比），而如果段演算法有三重遞歸，運算複雜度就會傾向 O(3^n)... 如此類推。無論講時間複雜度定空間複雜度，呢種情況都係唔理想嘅。因此，好多編程工作者都主張多重遞歸呢家嘢可免則免。

### 直接定間接

遞歸又可以分做**直接**同**間接**。直接遞歸係話個子程式會直接呼叫自己，而間接遞歸，又叫相互遞歸，就可以係個子程式呼叫另外一個子程式，而另外嗰個子程式又會呼叫返原先嗰個子程式。

相互遞歸都有唔少用途。有限狀態機就可以透過相互遞歸演算法嚟實現。一部有限狀態機會有若干個「狀態」，每個狀態涉及嘅行為都唔同。例如電子遊戲入便嗰啲 AI 技術就成日會用到有限狀態機，想像而家要製作一隻動作遊戲，遊戲入便嘅 AI 敵人有若干個狀態，就可以用好似以下噉嘅虛擬碼，嚟教電腦點樣控制呢啲敵人：

:**子程式** *ceon lo* () *# 巡邏*
::**如果** 見到玩家角色，就 *zeoi bou* ()
::**否則** 繼續做巡邏要做嘅嘢。
:**子程式** *zeoi bou* () *# 追捕*
::**如果** 玩家角色進入射程，就 *gung gik* ()
::**如果** 玩家角色離開視線，就 *ceon lo* ()
::**否則** 繼續做追捕要做嘅嘢。
:**子程式** *gung gik* () *# 攻擊*
::**如果** 玩家角色離開射程，就 *zeoi bou* ()
::**否則** 繼續做攻擊要做嘅嘢。

就算到咗廿一世紀初，呢種控制遊戲敵人嘅技術都仲好多人用。

### 係咪擺尾

尾遞歸係指叫部電腦遞歸嗰一句嘢，係成個子程式最後嗰句陳述式：一旦行咗嗰句嘢，個子程式就算係成個行晒；而且部電腦冇需要紀錄住打前嗰個狀態。例如以下呢個子程式

:**呢個子程式叫** print_saai(n) *# print 晒*
::如果 n x-1 = 0 嘅地步。部機跟住要做 `fac(0)`，出 `1`，然後佢要再計 `1*1` 嘅數，先至可以算係搞掂 `fac(1)`。喺部機行緊 `fac(0)` 嗰段期間，部機要記住「`fac(1)` 個 `x` 係幾多」呢一項資訊。因此，呢個子程式唔算係尾遞歸。一個子程式用咗尾遞歸，表示每行一個新嘅遞歸呼叫，之前嗰個呼叫就算係解決咗（部機唔使再記住嗰個呼叫嘅嘢），而呢點可以令到個程式用起記憶體上嚟更有效率。

## 遞歸實行
### 包裝函式

包裝函式係指一個「包裝住」另外一個子程式嘅子程式。如果呢種程序攞嚟同一個遞歸程序一齊用嘅話，通常會係類似噉：
:**Def** 遞歸程序 (n)
::遞歸程序要做嘅嘢...
:
:**Def** 包裝程序 (n)
::包裝程序要行嘅運算...
::Call 個遞歸程序
:
:然後主程式會 call 個包裝程序
噉嘅話主程式行起上嚟，就會行咗個包裝程序先，然後再開始進入遞歸嘅狀態。

「包裝程序要行嘅運算」可以係好多有用嘅功能，例如係事前處理啲 input 嘅數值或者係檢查吓啲 input 係咪合乎某啲條件（例如想確保入落去遞歸程序嘅數細過某啲指定數值）呀噉。呢種做法被指有好多好處——將事前處理等嘅嘢分離咗出嚟，交畀包裝程序處理，就可以達到模塊化嘅效果，令到啲源碼更易打理。

## 出名應用

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

## 對比疊代

同遞歸一樣，疊代程序都係一種用嚟重複某啲操作嘅技巧。

## 理論分析

## 睇埋
*自指
*鏈結串列
*最大最小化

## 文獻

*Bible, P. W., & Moser, L. (2023). *An Open Guide to Data Structures and Algorithms*. Palni Open Press. **2. Recursion**
*Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). *Introduction to algorithms*. MIT press. **4.4 The recursion-tree method for solving recurrences**
*Dijkstra, Edsger W. (1960). "Recursive Programming". *Numerische Mathematik*. 2 (1): 312–318. doi:10.1007/BF01386232.

## 參考
註釋：

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

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

## 拎

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