スマートフォン用の表示で見る

再帰

【recursion】

ある対象xの定義にx自身を使用することを再帰といい、そのような定義を再帰的定義という。もちろん、そのような定義は定義として成立する場合としない場合があり、再帰的定義が本当に定義になっていることは証明が必要である。

再帰は、プログラミング言語におけるデータ構造や関数の定義に用いられることが多い。関数の場合は、自分自身を繰り返し呼び出して、呼び出した順に処理が行われて再び帰ってくることから、「再帰」という名前がつけられたのであろう。

数列の漸化式は再帰的定義の一種である。通常は右辺の添字が左辺の添字より常に小さく、自然数である添字が無限に減少することはありえないので、定義として成立することがわかる。

再帰により定義されたデータ構造は再帰的データ構造ないし再帰データ構造と呼ばれる。リストや木は再帰データ構造の例である。

再帰により定義された関数再帰関数ないし再帰関数と呼ばれる。再帰関数の定義が定義として成立していないと、実行した場合の現象としては無限ループになる。

再帰データ構造に対する処理は、再帰関数を用いると自然に記述できることが極めて多い。