第1單元 遞迴

第1單元 遞迴

　

遞迴(recursion)在資訊科學上是一項十分重要的觀念與技巧，能夠了解並正確應用遞迴有助於許多複雜問題的解決。
在日常生活中，我們經常會碰到利用自己本身定義自己的例子，例如：
　(1)N的階乘(factorial )
　 0! = 1
　 N! = N*(N-1)!， 若N>0
　(2)費氏數列(Fibanacci number)
　 Fn= 0 　 , n<0 　 1 　 , n=1 　 Fn-1+Fn-2　, n>1
因此凡是事件由本身所定義者，便具遞迴關係。
　
就程式語言的觀點而言，遞迴是指「一程式呼叫自己本身(call ittself)」，在高階語言，C、Pascal、Quick BASIC及人工智慧語言Lisp、Prolog都提供了遞迴呼叫的功能，依據呼叫形式的不同，又可分為：
(1)直接遞迴：副程式或函數P直接呼叫自己本身
(2)間接遞迴：副程式或函數P呼叫另一副程式或函數Q，而副 程式或函數Q又呼叫副程式或函數P
　
就解決問題的角度而言，遞迴則是將一個複雜而無法立即解決的問題，透過某種方式(遞迴關係)將其逐步簡化或縮小規模，一直到我們能夠處理為止。
舉例來說：若我們要計算N階乘(factorial )之值，根據定義
N! = 1*2*3*….*(N-1) * N = (N-1)! * N
因此只要能求出(N-1)!，再乘上N即可得N!
要如何求出 (N-1)!之值呢?
　(N-1)!= 1*2*3*….*(N-2) * (N-1)= (N-2)! * (N-1)
因此只要能求出(N-2)!，再乘上N-1即可得(N-1)!
……
如此逐步將欲計算的值縮小規模，直到最後1!=1，便可以將結果逐步回傳。