遞歸算法

遞歸算法（英語：recursion algorithm）在計算機科學中是指一種通過重複將問題分解為同類的子問題而解決問題的方法。遞歸式方法可以被用於解決很多的計算機科學問題，因此它是計算機科學中十分重要的一個概念。絕大多數程式語言支持函式的自調用，在這些語言中函式可以通過調用自身來進行遞歸。計算理論可以證明遞歸的作用可以完全取代循環，因此在很多函式程式語言（如Scheme）中習慣用遞歸來實現循環。

基本介紹

• 中文名：遞歸算法
• 外文名：recursive algorithm
• 屬性：計算機算法
• 實現過程：一般通過函式或子過程來實現
• 特點：遞歸就是在過程或函數裡調用自身

遞歸程式

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

這一程式在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程式同樣計算一個數字的階乘，但是使用尾部遞歸：

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

能夠解決的問題

1. 數據的定義是按遞歸定義的。如Fibonacci函式。
2. 問題解法按遞歸算法實現。如Hanoi問題。
3. 數據的結構形式是按遞歸定義的。如二叉樹、廣義表等。

遞歸數據

數據類型可以通過遞歸來進行定義，比如一個簡單的遞歸定義為自然數的定義：“一個自然數或等於0，或等於另一個自然數加上1”。Haskell中可以定義鍊表為：

data ListOfStrings = EmptyList | Cons String ListOfStrings

這一定義相當於宣告“一個鍊表或是空串列，或是一個鍊表之前加上一個字元串”。可以看出所有鍊表都可以通過這一遞歸定義來達到。