遞歸算法（英語：recursion algorithm）在計算機科學中是指壹種通過重復將問題分解為同類的子問題而解決問題的方法。
遞歸式方法可以被用於解決很多的計算機科學問題，因此它是計算機科學中十分重要的壹個概念。絕大多數編程語言支持函數的自調用，在這些語言中函數可以通過調用自身來進行遞歸。
計算理論可以證明遞歸的作用可以完全取代循環，因此在很多函數編程語言（如Scheme）中習慣用遞歸來實現循環。
遞歸程序
在支持自調用的編程語言中，遞歸可以通過簡單的函數調用來完成，如計算階乘的程序在數學上可以定義為：
這壹程序在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))
能夠解決的問題
數據的定義是按遞歸定義的。如Fibonacci函數。
問題解法按遞歸算法實現。如Hanoi問題。
數據的結構形式是按遞歸定義的。如二叉樹、廣義表等。
參考資料
百科-遞歸算法.百度百科[引用時間2018-4-2]