本頁使用了標題或全文手工轉換

遞迴 (電腦科學)

維基百科,自由的百科全書
(已重新導向自 Recursion)
前往: 導覽搜尋

遞迴英語recursion)在電腦科學中是指一種通過重複將問題分解為同類的子問題而解決問題的方法。[1] 遞迴式方法可以被用於解決很多的電腦科學問題,因此它是電腦科學中十分重要的一個概念。[2] 絕大多數程式語言支援函式的自呼叫,在這些語言中函式可以通過呼叫自身來進行遞迴。計算理論可以證明遞迴的作用可以完全取代迴圈,因此在很多函數程式語言(如Scheme)中習慣用遞迴來實現迴圈。

電腦科學家尼克勞斯·維爾特如此描述遞迴:

遞迴的強大之處在於它允許使用者用有限的語句描述無限的物件。因此,在電腦科學中,遞迴可以被用來描述無限步的運算,盡管描述運算的程式是有限的。

遞迴程式[編輯]

在支援自呼叫的程式語言中,遞迴可以通過簡單的函式呼叫來完成,如計算階乘的程式在數學上可以定義為:

 \operatorname{fact}(n) =
 \begin{cases}
 1 & \mbox{if } n = 0 \\
 n \cdot \operatorname{fact}(n-1) & \mbox{if } n > 0 \\
 \end{cases}

這一程式在Scheme語言中可以寫作:

(define (factorial n)
  (if (= n 0)
      1
      (* n (factorial (- n 1)))))

不動點組合子[編輯]

即使一個程式語言不支援自呼叫,如果在這語言中函式第一類物件(即可以在執行期創建並作為變數處理),遞迴可以通過不動點組合子英語Fixed-point combinator)來產生。以下Scheme程式沒有用到自呼叫,但是利用了一個叫做Z 算子英語Z combinator)的不動點組合子,因此同樣能達到遞迴的目的

(define Z
  (lambda (f)
    ((lambda (recur) (f (lambda arg (apply (recur recur) arg))))
     (lambda (recur) (f (lambda arg (apply (recur recur) arg)))))))
 
(define fact
  (Z (lambda (f)
       (lambda (n)
         (if (<= n 0)
             1
             (* n (f (- n 1))))))))

這一程式思路是,既然在這裡函式不能呼叫其自身,我們可以用 Z 組合子應用(application)這個函式後得到的函式再應用需計算的參數。

尾端遞迴[編輯]

尾端遞迴是指遞迴函式在呼叫自身後直接傳回其值,而不對其再加運算。尾端遞迴與迴圈是等價的,而且在一些語言(如Scheme中)可以被優化為迴圈指令。 因此,在這些語言中尾端遞迴不會佔用呼叫堆疊空間。以下Scheme程式同樣計算一個數字的階乘,但是使用尾端遞迴[4]

(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* counter product)
              (+ counter 1))))
  (iter 1 1))

遞迴資料[編輯]

資料型別可以通過遞迴來進行定義,比如一個簡單的遞迴定義為自然數的定義:「一個自然數或等於0,或等於另一個自然數加上1」。Haskell中可以定義連結串列為:

data ListOfStrings = EmptyList | Cons String ListOfStrings

這一定義相當於宣告「一個連結串列或是空串列,或是一個連結串列之前加上一個字串」。可以看出所有連結串列都可以通過這一遞迴定義來達到。

參考文獻[編輯]

  1. ^ Graham, Ronald; Donald Knuth, Oren Patashnik. Concrete Mathematics. 1990: Chapter 1: Recurrent Problems (英文). 
  2. ^ Epp, Susanna. Discrete Mathematics with Applications 2nd. 1995: 427 (英文). 
  3. ^ Wirth, Niklaus. Algorithms + Data Structures = Programs. Prentice-Hall. 1976: 126 (英文). "The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions." 
  4. ^ Harold Abelson and Gerald Jay Sussman with Julie Sussman. Structure and Interpretation of Computer Programs. Cambridge, MA: MIT Press. 1996 [2011]. ISBN 0-262-01153-0 (英文).