遞歸
跳去導覽
跳去搵嘢
遞歸(粵拼: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,行呢段程式會發生以下嘅事:
- 個程式行
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.