再帰

自分自身を含む定義という不思議

「辞書」を辞書で引くと「語の意味を説明した本」とある。ではその「意味」を辞書で引くと…。この逸話は再帰の本質を直感的に示す。再帰（Recursion）とは、定義・手続き・構造が自分自身を含む性質のことであり、プログラミングから数学、言語学、そして哲学に至るまで遍在する根本的な概念だ。GEB（ゲーデル、エッシャー、バッハ）においてホフスタッターは再帰を自己言及と並ぶ中心的テーマとして徹底的に探求した。

再帰の定義

再帰的定義は二つの部分からなる。

基底ケース（base case）: 再帰を停止する条件。これがなければ無限ループになる。

再帰的ステップ（recursive step）: 問題を自分自身の「より小さい」バージョンに還元する規則。

自然数の定義の古典的例：0は自然数である（基底ケース）。nが自然数ならばn+1も自然数である（再帰的ステップ）。この二行で自然数の無限集合全体が定義される。

プログラミングにおける階乗の計算：factorial(0) = 1、factorial(n) = n × factorial(n-1)。関数が自分自身を呼び出す。このシンプルな形式が、複雑な計算を簡潔に表現できる。

事例分析：言語・音楽・視覚

言語における再帰の例として、名詞句の中に名詞句が埋め込まれる現象がある。「太郎が好きな花子が読んだ本」では、「太郎が好きな花子」という節が「本を読んだ主語」として機能し、さらに深い埋め込みが理論上無限に可能だ。言語学者ノーム・チョムスキーは、人間言語のこの再帰能力が有限の文法規則から無限の文を生成できる源泉だと論じた。

バッハの音楽に登場するカノンとフーガは音楽的再帰の体現だ。ある声部が別の声部を「追いかける」カノンでは、主題が変奏されながら繰り返し現れる。バッハの「Musical Offering」のクラブ・カノンは前後どちらから弾いても同じ音楽になる。ホフスタッターはこれを奇妙な環の音楽的表現として論じた。

エッシャーの版画「ギャラリー」では、画廊の中に飾られた絵の中に画廊が描かれている。この絵の絵の絵は理論上無限に続く。視覚的な再帰の完璧な表現だ。

対立概念：反復（イテレーション）との違い

再帰とよく混同される概念に反復（iteration）がある。反復はループ（for文・while文）を使って同じ処理を繰り返す。再帰は関数が自分自身を呼び出す。

同じ結果を出す処理も、多くの場合、再帰としても反復としても書ける。階乗計算は再帰でも for ループでも実装できる。ただし再帰的に定義された問題（木構造の探索など）は再帰で書く方が自然で理解しやすい。

理論的には、チャーチ＝チューリングのテーゼのもとで再帰関数と反復計算は等価な計算能力を持つ。しかし表現論的・認知的には、再帰のほうが「自己参照」という意味の層を持つ点で根本的に異なる。

応用

ゲーデル数の仕組みは、形式体系に「自分自身を計算対象とする」再帰的能力を与えた。奇妙な環は再帰的構造の中でも特に階層を閉じてしまうものとして、ホフスタッターが最も注目した形態だ。

形式体系における証明可能性の概念は、再帰的（原始再帰的）関数の理論と深く結びついている。何が「計算可能」かは、何が再帰的に定義できるかと等価であることが示されている。

人工知能においては、再帰ニューラルネットワーク（RNN）が時系列データ処理に使われる。自分自身の前の出力を次の入力として使うという、再帰の計算論的実装だ。より最近のTransformerアーキテクチャも、アテンション機構を通じた暗黙の再帰的処理を含む。

再帰は「無限を有限で語る」ための言語だ。有限の規則から無限の構造を生み出す能力。この能力が言語・数学・音楽・計算の根底に流れていることを、GEBは繰り返し示した。