再帰
ある対象xの定義にx自身を使用することを再帰といい、そのような定義を再帰的定義という。
もちろん、そのような定義は定義として成立する場合としない場合があり、再帰的定義が本当に定義になっていることは証明が必要である。
再帰は、プログラミング言語におけるデータ構造や関数の定義に用いられることが多い。
関数の場合は、自分自身を繰り返し呼び出して、呼び出した順に処理が行われて再び帰ってくることから、「再帰」という名前がつけられたのであろう。
数列の漸化式は再帰的定義の一種である。
通常は右辺の添字が左辺の添字より常に小さく、自然数である添字が無限に減少することはありえないので、定義として成立することがわかる。
再帰により定義されたデータ構造は再帰的データ構造ないし再帰データ構造 と呼ばれる。
リストや木構造は再帰データ構造の例である。
再帰により定義された関数は再帰的関数ないし再帰関数と呼ばれる。
再帰関数の定義が定義として成立していないと、実行した場合の現象としては無限ループになる。
再帰データ構造に対する処理は、再帰関数を用いると自然に記述できることが極めて多い。
recursion
帰納（Induction）
回帰（regression）
数学
数学的帰納法
再帰理論
帰納的集合（Recursive set）
帰納的可算集合
帰納言語
帰納的可算言語
帰納的関数
原始再帰関数
漸化式
計算機科学
再帰呼び出し 、再帰的呼び出し、リカーシブコール（recursive call）
末尾再帰、末端再帰、終端再帰（tail recursion）
原始再帰関数（Primitive Recursive Function）
相互再帰（Mutual recursion）
分割統治（divide and conquer）
入れ子、ネスティング（nesting）
再帰下降構文解析（Recursive Descent Parsing）
再帰データ型（Recursive Type）
ハノイの塔（Tower of Hanoi）
クイックソート（quick sort）
https://ja.wikipedia.org/wiki/再帰