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