1 定義と基本概念
1.1 再帰の定義
再帰とは、ある対象やプロセスがその定義や操作において自己自身を参照する性質を指す。数学や計算機科学、言語学など多岐にわたる分野で現れ、有限の記述から無限の構造や操作を生成する手段となる。再帰的な定義では、あるものがそのより単純なバージョンを用いて定義される。
1.2 ベースケースと再帰ステップ
再帰は通常、二つの要素から構成される。ベースケース（基底）は再帰の終了条件であり、これ以上分解できない最小のケースを定義する。再帰ステップは、対象をより単純な自己参照に分解し、最終的にベースケースに到達するよう設計される。適切なベースケースが存在しない場合、無限ループやスタックオーバーフローが発生する。
1.3 再帰と帰納の関係
数学的帰納法と再帰は深く関連している。帰納法は命題を証明する技法であり、再帰は関数や構造を定義する技法である。両者ともベースケースと、それより小さいケースへの依存関係を利用し、有限のステップで無限の対象を扱う。再帰的定義は帰納的証明の自然な対象となる。
2 数学における再帰
2.1 再帰的定義の例
2.1.1 階乗関数
階乗関数n!は、以下のように再帰的に定義される：
- ベースケース：0! = 1
- 再帰ステップ：n! = n × (n-1)! （n > 0の場合）
この定義は、任意の非負整数に対して一意に値を定める。
2.1.2 フィボナッチ数列
フィボナッチ数列F(n)は次のように定義される：
- ベースケース：F(0) = 0, F(1) = 1
- 再帰ステップ：F(n) = F(n-1) + F(n-2) （n ≥ 2の場合）
この定義は自然な再帰構造を持つが、単純な実装では指数関数的な計算量となる。
2.2 再帰的関数と原始再帰
原始再帰関数は、自然数上の関数のクラスであり、ゼロ関数、後者関数、射影関数を基本とし、合成と原始再帰によって定義される。原始再帰では、関数の定義に自身のより小さい引数での値のみを用いることが許される。原始再帰関数は常に停止するが、アッカーマン関数のような一般再帰関数は原始再帰では定義できない。
2.3 不動点と自己参照
数学において、関数fの不動点とはf(x)=xを満たすxである。再帰的な定義はしばしば不動点の存在と関連し、特にラムダ計算や圏論では、自己参照を不動点作用素を用いて表現する。不動点定理は再帰的定義の存在と一意性を保証する数学的基盤を提供する。
3 コンピュータ科学における再帰
3.1 再帰的アルゴリズム
3.1.1 分割統治法
分割統治法は、問題をより小さな同種の部分問題に分割し、各部分問題を再帰的に解いてから結果を結合する手法である。代表的な例としてマージソートやクイックソートが挙げられる。この手法は、問題のサイズが十分小さくなったときにベースケースとして直接解を返す。
3.1.2 バックトラッキング
バックトラッキングは、可能な解を探索する過程で行き詰まった場合に一歩戻り、別の選択肢を試すアルゴリズム手法である。再帰を用いて探索空間を深さ優先で走査し、条件を満たさない部分解を早期に破棄する。Nクイーン問題や数独の解法などに応用される。
3.2 再帰的データ構造
3.2.1 リストと木構造
リストは、要素と「残りのリスト」として再帰的に定義できる。木構造は、根ノードとその子ノードの集合（各子ノードもまた木構造）として定義される。二分探索木やヒープは、再帰的構造を持つデータの典型例であり、再帰的アルゴリズムで効率的に操作できる。
3.2.2 グラフの再帰的走査
グラフの深さ優先探索（DFS）は再帰的に実装される。訪問済みノードを記録しながら、各ノードから未訪問の隣接ノードへ再帰的に進む。この手法は連結成分の判定、トポロジカルソート、木構造の巡回などに広く用いられる。
3.3 再帰の実装とスタック
再帰的関数呼び出しは、コールスタックを用いて実装される。関数が自身を呼び出すたびに、新しいフレームがスタックに積まれ、ローカル変数や戻りアドレスが保存される。ベースケースに到達すると、スタックからフレームが順にポップされ、計算結果が戻される。深い再帰はスタックオーバーフローを引き起こす可能性がある。
3.4 末尾再帰と最適化
末尾再帰は、再帰呼び出しが関数の最後の操作として行われ、その結果がそのまま返される形式である。一部のコンパイラは末尾再帰最適化を行い、新しいスタックフレームを割り当てずにジャンプ命令に変換することで、反復と同等の効率を実現する。適切に設計された末尾再帰は、深い再帰を安全に実行できる。
3.5 再帰と反復の比較
再帰と反復は相互に変換可能な場合が多い。再帰は問題を直観的に表現できるが、関数呼び出しのオーバーヘッドやスタック消費のリスクがある。反復は効率的だが、複雑な自己参照構造の実装には手間がかかる。現実のプログラミングでは、問題の性質と実行環境に応じて適切な手法が選択される。
4 言語学における再帰
4.1 生成文法と再帰的規則
ノーム・チョムスキーに代表される生成文法理論では、言語の無限性を説明するために再帰的規則が用いられる。例えば、名詞句（NP）は「冠詞＋形容詞＋名詞＋関係節」として定義でき、関係節自体が名詞句を含むことができる。これにより有限の規則から無限の文を生成できる。
4.2 埋め込み構造と階層性
言語における再帰は、文中への文の埋め込みとして現れる。「太郎が花子が好きだと思っている」という日本語の文では、「花子が好きだ」という文が主文に埋め込まれている。このような中心埋め込みは処理が困難になることが知られており、人間の言語処理の限界を示す例として研究されている。
4.3 再帰性の普遍性と議論
チョムスキーらは、再帰性が人間言語の普遍的特性であり、他の動物のコミュニケーションシステムには見られないと主張した。しかし、一部の研究者は、特定の言語（例えばアマゾンのピダハン語）に再帰構造が欠如している可能性を指摘し、再帰性の普遍性に疑問を投げかけている。この議論は現在も続いている。
5 日常と文化における再帰
5.1 再帰的ユーモアとジョーク
5.1.1 自己言及的な言葉遊び
「この文には三つの誤りがある。一つ目は…」という形式のジョークは、自己言及の再帰性を利用する。また、「再帰を理解するには、まず再帰を理解する必要がある」という定義は、再帰的な教示法のパロディとして知られる。これらの言葉遊びは、再帰的構造に内在するユーモアを引き出す。
5.1.2 再帰的定義のパロディ
辞書における「再帰：再帰を参照」という自己参照的な定義は、よく知られたジョークである。また、「「すでに十分に定義されています」」という定義を参照する定義」のような無限後退のパロディも存在する。これらのユーモアは、特にプログラマや数学者の間で親しまれている。
5.2 再帰的思考とパラドックス
5.2.1 自己言及のパラドックス
「この文は偽である」という嘘つきのパラドックスは、自己言及が論理的矛盾を生む典型例である。同様に、「集合Xは、自身を要素として含まないすべての集合の集合である」というラッセルのパラドックスは、集合論における再帰的自己参照がもたらす問題を示す。
5.2.2 無限後退と興味深いループ
「すべての原因には原因がある」という主張は無限後退に陥る。芸術や音楽では、エッシャーの『描く手』やバッハのカノンなど、自己参照的な「興味深いループ」が探求されてきた。これらの作品では、再帰的構造が美的体験や哲学的洞察を生み出す。
6 関連概念と発展
6.1 相互再帰
相互再帰は、複数の関数やオブジェクトが互いを参照し合う形態である。例えば、関数Aが関数Bを呼び出し、関数Bが関数Aを呼び出す場合、これらは相互再帰の関係にある。言語処理における字句解析と構文解析、またはAIにおける二つのプレイヤーの戦略など、現実のシステムで頻繁に現れる。
6.2 高階再帰
高階再帰では、再帰的な処理が関数そのものを引数として受け取ったり、関数を返却したりする。関数型プログラミングにおいて、不動点コンビネータ（Yコンビネータ）は、ラムダ計算で再帰を実現する高階関数として知られる。高階再帰は、より抽象的な計算モデルの構築に貢献する。
6.3 再帰と計算可能性の限界
再帰的関数は計算可能性理論の中心的概念である。チューリングマシンで計算可能な関数は、再帰的関数と等価であることが示されている。しかし、停止問題のように、いかなる再帰的アルゴリズムでも解けない問題が存在する。再帰の持つ自己参照性は、数学の不完全性定理とも深く関わっている。