遞歸

出自維基百科,自由嘅百科全書
Jump to navigation Jump to search

遞歸粵拼dai6 gwai1英文recursion)喺程式編寫上係指一個子程式用到佢自己,例如以下呢段簡單嘅[1]

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

喺編程上,遞歸可以用嚟解決一啲可以揼散做一大柞細問題嘅問題,而且當中每一個細問題都屬同一個類型,例如以下嘅遞歸程式可以用嚟計階乘(factorial)[1]

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.

[編輯]