遞歸 (電腦科學)

出自維基百科,自由嘅百科全書
跳去導覽 跳去搵嘢

遞歸dai6 gwai1英文recursion)喺程式編寫上,如果係講緊子程式嘅定義,狹義上係指子程式嘅定義會直接用到[註 1]自己,廣義上就指子程式會直接或者間接用到自己[1]:41;如果講子程式嘅執行,指嘅係指子程式會直接或者間接啟動[註 2]自己[1]:121。遞歸可以用來將一條問題分做條問題「細啲嘅版本」噉嚟解[2]

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

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

應用[編輯]

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

計階乘[編輯]

例如以下嘅遞歸程式可以用嚟計階乘(factorial)[2]

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」,

睇埋[編輯]

文獻[編輯]

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

[編輯]

  1. 理論上跟數學講 apply,編程通常講 call
  2. 理論上講 activate,編程通常叫 call

[編輯]

  1. 1.0 1.1 1.2 1.3 1.4 Sethi, Ravi (1990) [1989]. Programming Languages: Concepts and Constructs. Reading, MA: Addison-Wesley. ISBN 0-201-10365-6.
  2. 2.0 2.1 Jaimini, Vaibhav. "Recursion and Backtracking".

[編輯]