再帰

出典: フリー百科事典『ウィキペディア（Wikipedia）』

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

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

[編集] 再帰呼び出し

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

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

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を乗じたもの。再帰呼び出し */
}

Lispによる例。

;;; 階乗n!を計算する
(defun fact (n)
  (or (and (zerop n) 1) ; 脱出条件。0!は1である
      (* n (fact (1- n))))) ; n!は(n-1)にnを乗じたもの。再帰呼び出し

VBAによる例。

Sub fact(n, r)
Rem 階乗n!を計算する
Dim w_n As Long            '再帰呼び出しの入力の変数
Dim w_r As Long            '再帰呼び出しの結果の変数
If n = 0 Then              '脱出の条件は0!である
  r = 1                    '0!は、1である
Else                       'ゼロ以外の場合
  w_n = n - 1              '再帰呼び出しの入力の変数を、nに1マイナスした値とする。
  Call fact(w_n, w_r)      '再帰呼び出しを行う
  r = w_r * n              '再帰呼び出しで得られた値にnを乗ずる
End If
End Sub

[編集] 類似した概念

[編集] 関連項目

[編集] 一般

[編集] 数学

[編集] 計算機科学

[編集] 日常社会

再帰的頭字語

[編集] 文芸

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

再帰