再帰

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

主に英語のrecursionとその派生語の訳にあてられる。他にrecurrenceの訳（回帰#物理学及び再帰性を参照のこと）や、reflexiveの訳として「再帰」が使われることがある。数学的帰納法との原理的な共通性から、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 を乗じたもの。再帰呼出し */
}

自身を呼び出す手法なので、引数が同じ値のままとなって再帰終了条件を満たさないというような状況にならないよう、値の変化に注意する必要がある。

再帰的データ構造

リンクリストや木構造は、要素（ノード）の型の中にその要素型自身への参照が存在するようなデータ型を用いて実現される。これは再帰的データ構造（再帰データ型）である。再帰的データ構造の探索には、再帰呼び出しを使うことが多い。

類似した概念

• 帰納
• 回帰

関連項目

一般

• 再帰性
• 再帰的定義
• 相互再帰

数学

• 数学的帰納法
• 再帰理論
• 帰納的集合
• 帰納的可算集合
• 帰納言語
• 帰納的可算言語
• 帰納的関数
• 原始再帰関数
• 漸化式
• 高階関数

計算機科学

• 末尾再帰
• 分割統治法
• ネスティング
• 再帰下降構文解析
• 再帰データ型
• ハノイの塔 - プログラムの例題としてよく登場する。
• リカーシブスローダウン

日常社会

• 再帰的頭字語

文芸

• 落語『頭山』 ストーリーに再帰が現れる。