遞歸 (電腦科學)

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

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

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

應用

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

計階乘

例如以下嘅遞歸程式可以用嚟計階乘（factorial）：

function factorial(x)
    if x is 0
        return 1
    return x * factorial(x-1)

如果個輸入值（x）係 5，行呢段程式會發生以下嘅事：

1. 個程式行 return x * factorial(x-1)，呢個子 factorial 以 4 做輸入；
2. 個程式行 return x * factorial(x-1)，呢個子 factorial 以 3 做輸入；
3. 個程式行 return x * factorial(x-1)，呢個子 factorial 以 2 做輸入；
4. 個程式行 return x * factorial(x-1)，呢個子 factorial 以 1 做輸入；
5. 個程式行 return x * factorial(x-1)，呢個子 factorial 以 0 做輸入；
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$。

睇埋

• 子程式
• 控制流程
• 自指
• 鏈結串列
• 碎形

文獻

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

拎

• Introduction to Recursion - Data Structure and Algorithm Tutorials. GeeksForGeeks.