在計算機科學中，遞歸是一種解決計算問題的方法，其中的解決方案取決于同一問題的較小實例的解決方案。 遞歸通過使用從自己的代碼中調用自己的函數來解決此類遞歸問題。 該方法可以應用于多種類型的問題，遞歸是計算機科學的核心思想之一。

遞歸的力量顯然在于可以通過有限的語句定義無限的對象集。 同樣，有限遞歸程序可以描述無限次的計算，即使該程序不包含明確的重復。

—>Niklaus Wirth，算法 + 數據結構 = 程序，1976

大多數計算機編程語言通過允許函數從其自己的代碼中調用自身來支持遞歸。 一些函數式編程語言（例如，Clojure）沒有定義任何循環結構，而是僅依靠遞歸來重復調用代碼。 可計算性理論證明，這些只遞歸的語言是圖靈完備的； 這意味著它們與基于 while 和 for 等控制結構的命令式語言一樣強大（它們可用于解決相同的問題）。

從自身內部重復調用一個函數可能會導致調用堆棧的大小等于所有涉及的調用的輸入大小的總和。 由此可見，對于可以通過迭代輕松解決的問題，遞歸通常效率較低，對于大型問題，使用尾調用優化等優化技術是基礎。

一種常見的算法設計策略是將問題劃分為與原始問題類型相同的子問題，解決這些子問題，然后組合結果。 這通常被稱為分而治之的方法； 當與存儲先前解決的子問題的結果的查找表結合使用時（以避免重復解決它們并產生額外的計算時間），它可以稱為動態規劃或記憶。

一個遞歸函數定義有一個或多個基本情況，意思是函數產生結果的輸入（不重復），和一個或多個遞歸情況，意思是程序重復（調用自己）的輸入 . 例如，階乘函數可以通過方程 0! = 1 并且，對于所有 n > 0，n！ = n(n ? 1)!。 這兩個方程本身都不能構成完整的定義； xxx個是基本情況，第二個是遞歸情況。 因為基本案例打破了遞歸鏈，它有時也被稱為終止案例。

遞歸案例的工作可以看作是將復雜的輸入分解為更簡單的輸入。 在正確設計的遞歸函數中，對于每次遞歸調用，輸入問題必須以最終必須達到基本情況的方式進行簡化。 （在正常情況下不打算終止的函數——例如，一些系統和服務器進程——是一個例外。）忽略編寫一個基本案例，或者不正確地測試它，可能會導致無限循環。

對于某些函數（例如計算 e = 1/0！+ 1/1！+ 1/2！+ 1/3！+ ... 的系列），輸入數據沒有隱含明顯的基本情況 ; 對于這些，可以添加一個參數（例如在我們的系列示例中要添加的術語數）以提供建立基本案例的“停止標準”。 corecursion 更自然地處理這樣的例子，其中輸出中的連續項是部分和； 這可以通過使用索引參數來計算第 n 個項（第 n 個部分和）來轉換為遞歸。

許多計算機程序必須處理或生成任意數量的數據。 遞歸是一種表示程序員不知道確切大小的數據的技術：程序員可以使用自引用定義來指定此數據。 有兩種類型的自指定義：歸納定義和共歸納定義。

歸納定義的遞歸數據定義是指定如何構造數據實例的定義。 例如，可以歸納地定義鏈表（這里使用 Haskell 語法）：

數據 ListOfStrings = EmptyList | 缺點 String ListOfStrings

上面的代碼指定一個字符串列表為空，或者指定一個包含一個字符串和一個字符串列表的結構。 定義中的自引用允許構造任意（有限）數量的字符串列表。

歸納定義的另一個例子是自然數（或正整數）：

自然數是 1 或 n+1，其中 n 是自然數。

類似地，遞歸定義通常用于對編程語言中的表達式和語句的結構建模。