遞歸 (電腦科學)

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

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

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

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

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

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

如果個輸入值係 5，行呢段程式會發生以下嘅事：
個程式行 return x * factorial(x-1)，呢個子 factorial 以 4 做輸入；
個程式行 return x * factorial(x-1)，呢個子 factorial 以 3 做輸入；
個程式行 return x * factorial(x-1)，呢個子 factorial 以 2 做輸入；
個程式行 return x * factorial(x-1)，呢個子 factorial 以 1 做輸入；
個程式行 return x * factorial(x-1)，呢個子 factorial 以 0 做輸入；
因為 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」，。

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

文獻 
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.

編程