遞歸在計算機科學中是指一種通過重複将問題分解為同類的子問題而解決問題的方法。遞歸式方法可以被用于解決很多的計算機科學問題,因此它是計算機科學中十分重要的一個概念。
絕大多數編程語言支持函數的自調用,在這些語言中函數可以通過調用自身來進行遞歸。計算理論可以證明遞歸的作用可以完全取代循環,因此在很多函數編程語言中習慣用遞歸來實現循環。在支持自調用的編程語言中,遞歸可以通過簡單的函數調用來完成。尾部遞歸是指遞歸函數在調用自身後直接傳回其值,而不對其再加運算。尾部遞歸與循環是等價的,而且在一些語言可以被優化為循環指令。 因此,在這些語言中尾部遞歸不會占用調用堆棧空間。