再帰

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

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

再帰呼出し

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

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

再帰呼出しが実装されていない言語（BASIC、FORTRANなど）では、プログラマが、スタックなどを利用して再帰と同様の効果をえられる。

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

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

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

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

再帰呼出しの例

ここでは、階乗計算を例にとって各言語の再帰呼び出しのパターンを紹介する。

C言語での例：

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

JavaScript (ECMAScript) での例：

function fact(n) {
    return n ? n * fact(n - 1) : 1;
}

// JavaScript では arguments.callee プロパティ（自分自身を指す）
// によって、無名再帰を書くことができる。
var fact = function(n){
    return n ? n * arguments.callee(n - 1) : 1;
};

Lispでの例：

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

VBAでの例：

 Rem 階乗 n! を計算する
 Function fact(n) As Long
   Dim n As Long
   If n = 0 Then          ' 脱出条件
     fact = 1             ' 0! は 1 である
     Exit Function
   End If
   fact = fact(n - 1) * n ' n! は (n-1) に n を乗じたもの。再帰呼出し
 End Function

Pascalでの例；

 function fact(n : integer): integer;
 begin
   if n = 0 then {脱出条件。0! は 1 である}
     fact := 1
   else 
     fact := fact(n - 1) * n; {n! は (n-1)!*n である。再帰呼出し}
   end
 end;

Prologでの例;

% 階乗 n! を計算する。解は第二引数に得られる。
fact(0,1) :- !.             % !はさらに第一引数が -1,-2,...と計算が進むことがないようにする備え
fact(N,F) :-
    N_1 is N - 1,
    fact(N_1,F_1),          % Nから1を引いたN_1の階乗がF_1であれば、
    F is F_1 * N.　　　　   % 階乗は N に F_1 を乗じたものである。

類似した概念

• 帰納
• 回帰

関連項目

一般

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

数学

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

計算機科学

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

日常社会

• 再帰的頭字語

文芸

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