一個遞歸演算法必須包括什麼

遞歸演算法（英文：recursion algorithm）在電腦科學中是指一種透過重複將問題分解為同類的子問題而解決問題的方法。

遞歸式方法可以用來解決很多的電腦科學問題，因此它是電腦科學中十分重要的一個概念。

絕大多數程式語言支援函數的自調用，在這些語言中函數可以透過調用自身來進行遞歸。 （推薦學習：web前端影片教學）

計算理論可以證明遞歸的作用可以完全取代循環，因此在許多函數程式語言（如Scheme）中習慣用遞歸來實現循環。

遞迴程式

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

這程式在Scheme語言中可以寫：

(define (factorial n)  (if (= n 0)      1      (* n (factorial (- n 1)))))<br/>

不動點組合子

即使一個編程語言不支援自調用，如果在這語言中函數是第一類物件（即可以在運行期創建並作為變數處理），則遞歸可以透過不動點組合子（英語：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))))))))<br/>

以上是一個遞歸演算法必須包括什麼的詳細內容。更多資訊請關注PHP中文網其他相關文章！