遞歸

遞歸（粵拼：dai⁶ gwai¹；英文：recursion）喺程式編寫上係指一個子程式用到佢自己，例如以下呢段簡單嘅碼噉：

function dream()
    print "Dreaming"
    dream() // dream 呢個子程式當中用到自己。

喺編程上，遞歸可以用嚟解決一啲可以揼散做一大柞細問題嘅問題，而且當中每一個細問題都屬同一個類型，例如以下嘅遞歸程式可以用嚟計階乘（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.