在數學和計算機科學中，當壹類對象或方法可以由兩個屬性定義時，它們表現出遞歸行為:
簡單的基線條件---不使用遞歸產生答案的終止情況
壹組規則將所有其他情形縮減到基線條件
例如，以下是某人祖先的遞歸定義:
某人的父母是他的祖先(基線條件)
某人祖先的祖先也是他的祖先(遞歸步驟)
斐波那契數列是遞歸的經典例子:
Fib(0) = 1 基線條件1；
Fib(1) = 1 基線條件2；
對所有整數n,n > 1時：Fib(n) = (Fib(n-1) + Fib(n-2))。
許多數學公理基於遞歸規則。例如，皮亞諾公理對自然數的形式定義可以描述為:0是自然數，每個自然數都有壹個後繼數，它也是自然數。通過這種基線條件和遞歸規則，可以生成所有自然數的集合。
遞歸定義的數學對象包括函數、集合，尤其是分形。
遞歸還有多種開玩笑的“定義”。
非正式定義
遞歸是當程序的壹個步驟涉及調用程序本身的過程。經歷遞歸的過程被稱為“遞歸”。
要理解遞歸，必須認識到程序和程序運行之間的區別。程序是基於壹組規則的壹組步驟。程序的運行實際上包括遵循規則和執行步驟。壹個類比:壹個程序就像壹個書面的食譜；運行壹個程序就像實際準備飯菜壹樣。
遞歸與過程規範中對其他程序執行的引用相關，但不相同。例如，食譜可能指烹飪蔬菜，而需要依次加水等步驟是另壹個程序。然而，遞歸過程是指(至少)其中壹個步驟需要壹個相同過程的新實例，就像酸面團配方需要上次制作相同配方時剩下的壹些面團。這立即產生了壹個無限循環的可能性；如果為了程序能夠完成，在某些情況下跳過有問題的步驟，這樣遞歸只能在定義中被正確使用，比如壹個酸面團配方，它還告訴您如何獲取壹些生面團，以防您以前從未做過生面團。即使定義正確，遞歸過程對人類來說也不容易執行，因為它需要區分過程的新調用和舊調用(部分執行)；這需要對程序的各種同步實例的進展程度進行壹些管理。因此，遞歸定義在日常情況下非常罕見。壹個例子可以是下面的尋找迷宮之路的過程，繼續前進，直到到達出口或分支點(死角被認為是帶有0個分支的分支點)。如果到達的點是出口，終止。否則，遞歸地使用該過程，依次嘗試每個分支；如果每次試驗都只到達死胡同而失敗，返回到導致這個分支點的路徑並報告失敗。這是否真正定義了終止過程取決於迷宮的性質:它不允許循環。在任何情況下，執行該過程都需要仔細記錄所有當前探索的分支點，以及哪些分支已經被徹底嘗試過。
在語言中
語言學家諾姆·喬姆斯基和其他許多人都認為，壹種語言中語法句子數量沒有上限，語法句子長度也沒有上限(超出了實際的限制，例如說出來的時間)，這可以解釋為自然語言中遞歸的結果。 這可以用句法範疇的遞歸定義來理解，例如句子，壹個句子可以有壹個結構，在這個結構中，跟在動詞後面的是另壹個句子:多蘿西認為女巫是危險的，在這個結構中，女巫是危險壹句出現在更大的句子中。因此，壹個句子可以遞歸地(非常粗略地)定義為壹個結構，包括壹個名詞短語、壹個動詞和可選的另壹個句子。這實際上只是遞歸數學定義的壹個特例。
這提供了壹種理解語言創造的方法——無限數量的語法句子——因為它立即預言句子可以是任意長度的:多蘿西認為托托懷疑鐵皮人說的....除了可以遞歸定義的句子之外，還有許多結構，因此壹個句子可以通過許多方式將壹個類別的實例嵌入另壹個類別。多年來，壹般來說，語言都被證明適合這種分析。
然而，最近，丹尼爾·埃弗雷特基於他對皮拉漢語的主張，對遞歸是人類語言的壹個基本屬性這壹普遍接受的觀點提出了挑戰。Andrew Nevins, David Pesetsky 和 Cilene Rodrigues是許多反對這壹觀點的人之壹。 在任何情況下，文學自我引用都可以被認為不同於數學或邏輯遞歸。
遞歸不僅在語法中起著至關重要的作用，在自然語言語義中也是如此。例如，單詞and可以理解為壹種功能，它可以應用於句子含義，從而創造出新的句子，同樣也可以用於名詞短語含義、動詞短語含義和其它。它也適用於不及物動詞、及物動詞或雙及物動詞。為了給它提供壹個適當靈活的單壹表示，並且通常被定義為使得它可以將這些不同類型的含義中的任何壹種作為參數。這可以通過為壹個簡單的案例定義它來實現，在這個案例中，它組合了句子，然後根據簡單的案例遞歸地定義其他案例。
遞歸語法是壹種包含遞歸生成規則的形式語法。
遞歸幽默
遞歸有時在計算機科學、程序設計、哲學或數學教科書中幽默地使用，通常是通過給出循環定義或自我引用，在循環定義或自我引用中，假定的遞歸步驟不會更接近基線條件，而是導致無限回歸。這樣的書在詞匯表中包含壹個笑話條目並不罕見，大致如下：
另壹個笑話是“要理解遞歸，妳必須理解遞歸。” 在谷歌網絡搜索引擎的英文版本中，當搜索“遞歸”時，網站會提示“妳的意思是:遞歸？”Andrew Plotkin的另壹種形式如下:“如果妳已經知道遞歸是什麽，就記住答案。否則，找壹個比妳更靠近道Douglas Hofstadter 的人；然後問他或她什麽是遞歸。”
遞歸首字母縮寫也可以是遞歸幽默的例子。例如，PHP代表“PHP Hypertext Preprocessor”，WINE代表“WINE Is Not an Emulator.”，GNU代表“GNU's not Unix”。
在數學中
遞歸定義的集合
例子:自然數
遞歸定義集合的典型例子由自然數給出:
0是自然數；
如果n是自然數，那麽n+1也是自然數；
自然數集合是滿足前兩個屬性的最小集合。
例子:真正可達命題的集合
另壹個有趣的例子是公理系統中所有“真正可達”命題的集合。
如果壹個命題是公理，它就是壹個真正可達的命題。
如果壹個命題可以通過推理規則從真正可達命題中獲得，那麽它就是真正可達命題。
真正可達命題集是滿足這些條件的最小命題集。
這個集合被稱為“真正可達命題”，因為在數學基礎的非建設性方法中，真正命題的集合可能大於由公理和推理規則遞歸構造的集合。有限細分規則
有限細分規則是遞歸的幾何形式，可用於創建類似分形的圖像。細分規則從由有限多個標簽標記的多邊形集合開始，然後以僅依賴於原始多邊形標簽的方式將每個多邊形細分為更小的標記多邊形，這個過程可被叠代。創建康托集合的標準“中間三分之壹”技術是細分規則，重心細分也是細分規則。函數遞歸
壹個函數可以根據自身被部分地定義。壹個常見的例子是斐波那契數列: F(n) = F(n ? 1) + F(n ? 2)。為了使這樣的定義有用，它必須引入非遞歸定義的值，在這種情況下，F(0) = 0，F(1) = 1。
壹個著名的遞歸函數是阿克曼函數，它不同於斐波那契數列，如果沒有遞歸，它將無法被表達的。涉及遞歸定義的證明
如前幾節所述，將標準的案例證明技術應用於遞歸定義的集合或函數，會產生結構歸納法，這是數學歸納法的壹種強有力的推廣，廣泛用於數學邏輯和計算機科學中的推導證明。遞歸優化
動態規劃是壹種優化方法，它以遞歸的形式重述了多階段或多步驟優化問題。動態規劃的關鍵結果是貝爾曼方程(Bellman equation)，它將優化問題早期(或較早步驟)的值寫入到後期(或較晚步驟)的值中。遞歸定理
在集合論中，這是壹個保證遞歸定義函數存在的定理。給定壹個集合X,集合X中的壹個元素a和壹個函數f: X -->X，定理表明存在壹個唯壹的函數F：N-->X(N表示包括0的自然數集合)，使得滿足F(0)=a , F(n+1)=f(F(n)) (對於任何自然數n)。
唯壹性的證明
取兩個函數F：N-->X和G：N-->X使得滿足：
F(0)=a
G(0)=a
F(n+1)=f(F(n))
G(n+1)=f(G(n))
其中a是集合X中的壹個元素。
數學歸納法可以證明對於所有自然數都有F(n)=G(n)：
基線條件：當n=0時，等式F(0)=a=G(0)成立；
遞歸步驟：假設當k∈N時，F(k)=G(K)成立,然後F(k+1)=f(F(k))=f(G(k))=G(k+1),因此F(k)=G(k)意味著F(k+1)=G(k+1)
通過歸納，F(n)=G(n) (其中n∈N)。
在計算機科學中
壹種常見的簡化方法是將壹個問題分成相同類型的子問題。作為壹種計算機編程技術，這被稱為分治法，是許多重要算法設計的關鍵。分治法是壹種自上而下解決問題的方法，通過解決越來越小的實例來解決問題。相反的方法是動態編程，這種方法是自下而上的方法，通過解決越來越大的實例來解決問題，直到達到所需的大小。
遞歸的壹個經典例子是階乘函數的定義，這裏用C代碼給出:
unsigned int factorial(unsigned int n) {undefined
if (n == 0) {undefined
return 1;
} else {undefined
return n * factorial(n - 1);
}
}
該函數在輸入的較小版本(n-1)上遞歸調用自身，並將遞歸調用的結果乘以n，直到達到基線條件，類似於階乘的數學定義。
當壹個函數被定義為更簡單、通常更小的自身時，計算機編程中的遞歸就是壹個例子。然後通過組合從問題的簡單版本中獲得的解決方案來設計問題的解決方案。遞歸的壹個示例應用是在編程語言的解析器中。遞歸的最大優點是通過有限的計算機程序可以定義、解析或產生無限組可能的句子、設計或其他數據。
遞推關系是遞歸定義壹個或多個序列的方程，可以“解決”某些特定類型的遞推關系來獲得非遞歸定義。
在藝術領域
俄羅斯娃娃或俄羅斯套娃是遞歸概念的壹個物理藝術例子。
自1320年喬托的Stefaneschi三聯畫問世以來，遞歸就壹直用於繪畫。它的中央面板包含紅衣主教Stefaneschi的跪像，舉著三聯畫本身作為祭品。
M.C. Eschers 印刷畫廊 (1956)描繪了壹個扭曲的城市，其中包含壹個遞歸包含圖片的畫廊，因此無限。