再帰

再帰的から転送)

再帰(さいき)は、あるものについて記述する際に、記述しているものそれ自身への参照が、その記述中にあらわれることをいう。定義において、再帰があらわれているものを再帰的定義という。

主に英語のrecursionとその派生語の訳にあてられる。他にrecurrenceの訳(回帰#物理学及び再帰性を参照のこと)や、reflexiveの訳(再帰代名詞再帰動詞。また、社会学で、対象に対する言及がその対象自体に影響を与えること(en:Reflexivity (social theory)))として「再帰」が使われることがある。数学的帰納法との原理的な共通性から、recursionの訳として数学では「帰納」を使うことがある。

目次

再帰呼出し編集

再帰呼出し(さいきよびだし、 recursive call)は、プログラミング技法の一つである。

手続きや関数といった概念をもつプログラミング言語では、ある手続き中で再びその手続き自身を呼び出すことを認める場合が多い。これを再帰呼出しといい、階乗計算やフィボナッチ数列のように、本来再帰的な構造をもつアルゴリズム(再帰的アルゴリズム)を記述するのに適している。

再帰呼出しが許されない言語もある(戻りアドレスを固定の場所に記録しているなど。かなり昔のFORTRANなどではそういう実装もあった)。また、引数やローカル変数が無いため効果的に再帰呼出しを利用できない言語(クラシックなBASIC等)では、配列を利用してスタックを実装し、それを使って再帰的な処理を実現する。

複数の手続き/関数が互いに相手を呼ぶ場合も、広い意味での再帰呼出し(相互再帰)である。Pascal での例:

 procedure A;
 ...
 B
 ...
 end;
 
 procedure B;
 ...
 A
 ...
 end;

処理を中断・終了する条件(下の例では引数 n の値が 0 である場合)が必ず一つは必要で、その部分が誤っていると、無限に関数を呼び出し続けることがある(→暴走)。

再帰呼出しが正常に機能するためには、手続きがリエントラントである必要がある。

再帰呼出しの例編集

ここでは、階乗計算を再帰呼び出しにより実装する例を紹介する。

C言語での例:

/* 階乗 n! を計算する */
int fact(int n)
  { 
  if (n == 0) return 1;   /* 脱出条件。0! は 1 である */
  else return fact(n-1) * n; /* n! は (n-1)! に n を乗じたもの。再帰呼出し */
  }

自身を呼び出す手法なので引数が同じ値のままとなるような同じ状況が無限に続いてしまうケースがあり、この状況にならないように値の変化に注意する必要がある。

類似した概念編集

関連項目編集