Neblux 知識グラフ
再帰
再帰とは、あるプロセス・関数・構造がより単純またはより小さな自身の例によって定義されるという原理である。
概要
再帰は数学・論理学・コンピュータ科学において自己参照的な構造を扱う強力な道具として現れる。数学では自然数のペアノ公理や帰納的に定義された数列に再帰的定義が登場する。論理学では一九三〇年代にゲーデルとクライニーが形式化した再帰関数の概念が計算可能性理論の中核をなす。コンピュータ科学ではマージソートや深さ優先探索といった再帰的アルゴリズムが問題をより小さな部分問題に分解し、しばしば優雅かつ効率的な解をもたらす。適切に定義された再帰的プロセスに必要な重要条件は、自己参照の連鎖を終わらせる基底ケースの存在である。
なぜ重要か
再帰はプログラミング言語の基盤であり、木やグラフといった複雑なデータ構造を自己参照的定義によって実装することを可能にする。LispやHaskellのような関数型プログラミング言語の設計を形作った。この概念は言語学にも現れ、再帰的な句構造規則が人間言語の無限の生成能力を説明する。視覚芸術と音楽では再帰的パターンが自己相似構造を生み出し、ジェネラティブアートやアルゴリズム作曲に影響を与えた。自己参照のより広い哲学的意義——ゲーデルの定理とホフスタッターの重要な著作が探求した——は、再帰を二十世紀の重要な知的概念の一つとしている。