遞歸 (電腦科學)

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

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

遞歸的強大之處在於它允許用戶用有限的陳述式描述無限的物件。因此，在電腦科學中，遞歸可以被用來描述無限步的運算，儘管描述運算的程式是有限的。

——尼克勞斯·維爾特

遞歸程式

java

public void recursiveTest(){
    recursiveTest();  //自己调用自己，就叫递归
}

python

def RecursiveTest():
    RecursiveTest()  # 自己调用自己

以上兩個程式是最簡單的遞歸，但因為無限地呼叫自己而不會停下，就會因為棧空間溢位而導致程式產生異常而強制停止，而python會因為自身設置的保護措施（限定遞歸的迴圈次數，但該次數可更改）而不斷投擲異常。

所以如果想要設計一個遞歸程式，就必須注意設定一個表達式判斷（例如if陳述式）來告訴程式是否應該繼續遞歸下去。

應用

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

$\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程式同樣計算一個數字的階乘，但是使用尾端遞迴：

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

能夠解決的問題

1、數據的定義是按遞歸定義的。如費氏數列。

2、問題解法按遞歸演算法實現。如河內塔。

3、數據的結構形式是按遞歸定義的。如二叉樹、廣義表等。

遞歸資料

主條目：遞歸資料類型

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

data ListOfStrings = EmptyList | Cons String ListOfStrings

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