再帰
さいき概念
処理が自分自身を呼び出す考え方。木構造の探索や分割統治など、簡潔で強力なアルゴリズムを生む。
年表
1928ヒルベルトとアッカーマンが決定問題(Entscheidungsproblem)を定式化
1931ゲーデルが不完全性定理の論文で原始再帰の精密な定義を提示
1936チャーチが決定問題の解けないことを証明（チューリングも1937年に独立に証明）
概要
処理が自分自身を呼び出すという考え方。ある問題を、同じ形をした少し小さい問題に分解し、それを解くために自分自身をもう一度呼び出す、という手続きを繰り返すことで、木構造の探索や分割統治法など、簡潔で強力なアルゴリズムを組み立てられる。
時代背景
再帰という考え方の起源は数学の論理学にある。1928年、ダフィット・ヒルベルトとヴィルヘルム・アッカーマンが「決定問題（Entscheidungsproblem）」を定式化し、論理式が真かどうかを機械的に判定するアルゴリズムが存在するかを問うた。この問いに応える中で、1931年にクルト・ゲーデルが不完全性定理の論文で原始再帰の精密な定義を与え、1934年には「一般再帰関数」という、およそ計算可能なすべての関数を捉えようとする概念を導入した。1936年にアロンゾ・チャーチが、1937年にアラン・チューリングがそれぞれ独立に決定問題が解けないことを証明し、「一般再帰関数＝実効的に計算可能な関数」とする、いわゆるチャーチのテーゼへとつながっていった。数学の世界で長く使われてきた再帰が、実際にプログラミングの実用的な道具として使われ始めるのは1950年代末から1960年代初頭にかけてである。
現在
今日のプログラミング言語の多くは再帰呼び出しをサポートしており、木構造やグラフの探索、再帰下降パーサ、分割統治アルゴリズムなど、幅広い場面で標準的な道具として使われている。
関連項目
- 有限オートマトン状態と遷移で振る舞いを表す計算モデル。字句解析やプロトコル設計など、幅広い場面の土台となる。