Neblux 知識グラフ
再帰
再帰とは、ある対象を同種の構造を持つ他の事例に基づいて定義または計算する原理である。
概要
帰納的な定義では、通常、基底ケースと再帰的な規則を指定する。計算では、自分自身を直接呼ぶ場合も、他の関数を経由する場合もある。停止証明の一つの方法は、各再帰呼び出しで非負整数の尺度が厳密に減少し、基底ケースの処理が終了することを示すことである。これは十分な証明方法であり、再帰そのものの定義ではない。
なぜ重要か
再帰的な走査は木やグラフに利用できる。一般のグラフには閉路があり得るため、深さ優先探索では訪問済みの頂点を記録して繰り返しの探索を避けられる。再帰的な文法規則は文の入れ子もモデル化できる。これらは異なる応用例であり、すべてのグラフが階層構造を持つことを意味しない。