Neblux 知識圖譜
遞迴
遞迴是一種原則，使得一個過程、函式或結構可以用自身更簡單或更小的實例來定義。
概觀
遞迴在數學、邏輯與電腦科學中是處理自我參照結構的強大工具。在數學中，遞迴定義出現在自然數的皮亞諾公理與歸納定義的序列中。在邏輯上，哥德爾與克萊尼於一九三〇年代形式化的遞迴函式概念是可計算性理論的核心。在電腦科學中，合併排序與深度優先搜尋等遞迴演算法將問題分解為更小的子問題，往往得出優雅且高效的解。定義良好的遞迴過程的關鍵要求是存在一個終止自我參照鏈的基礎情況。
為什麼重要
遞迴是程式語言的基礎，使得樹與圖等複雜資料結構得以透過自我參照定義實現。它塑造了 Lisp 與 Haskell 等函數式程式語言的設計。此概念也出現在語言學中，遞迴的短語結構規則解釋了人類語言的無限生成能力。在視覺藝術與音樂中，遞迴模式產生自相似結構，影響了生成藝術與演算作曲。自我參照更廣泛的哲學意義——由哥德爾定理與霍夫斯塔德的重要著作所探索——使遞迴成為二十世紀最重要的智識概念之一。