WordNet

(mathematics) an expression such that each term is generated by repeating a particular mathematical operation

Wikipedia preview

出典(authority):フリー百科事典『ウィキペディア（Wikipedia）』「2016/10/14 23:35:28」(JST)

wiki ja

「リカーシブル」はこの項目へ転送されています。米澤穂信の小説については「リカーシブル (小説)」をご覧ください。

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

主に英語の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 である */
    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 を乗じたものである。

類似した概念

帰納
回帰

UpToDate Contents

全文を閲覧するには購読必要です。 To read the full text you will need to subscribe.

1. 予後良好な患者における脳転移の治療 treatment of brain metastases in favorable prognosis patients
2. 予後不良の患者における脳転移の治療 treatment of brain metastases in poor prognosis patients
3. 黒色腫（メラノーマ）の脳転移のマネージメント management of brain metastases in melanoma
4. 乳癌における脳転移のマネージメント management of brain metastases in breast cancer
5. 脳転移患者の臨床症状、診断、およびマネージメントの概要 overview of the clinical manifestations diagnosis and management of patients with brain metastases

Japanese Journal

一人称 : 私は何を意味するか

アンスコム[著],大辻正晴[訳]
文学部論叢 104, 115-137, 2013-03-10
A Japanese translation of G.E.M. Anscombe, "The First Person", an important article on the topic of the self. Anscombe argues that if "I" is a name it requires a conception, i.e. a way of being given, …
NAID 110009555210

動き補償と時空間フィルタによる低照度映像の画質改善

水田辰也,松田一朗,深井寛修,伊東晋
情報処理学会研究報告. [オーディオビジュアル複合情報処理] 2013-AVM-80(4), 1-5, 2013-02-15
… インコントロールなどで補正しようとしても,信号成分と同時に雑音成分まで強調されてしまうため,十分な画質を得ることが困難である.そこで,動き補償と時空間フィルタを用いて近傍画素値を積分し,仮想的に開口面積または露出時間を長くすることで,低照度映像の画質を改善する手法を提案する.また,画質改善後の画像を次フレームの処理に再帰的に利用し,処理遅延および演算量を低減する効果についても調査する. …
NAID 110009536460

Strassenのアルゴリズムを付加した行列積自動チューニングライブラリ

坂本真貴人 ,藤井昭宏 ,田中輝雄
情報処理学会研究報告. [ハイパフォーマンスコンピューティング] 2013-HPC-138(6), 1-7, 2013-02-14
… 行列行列積を計算する DGEMM の性能は,さまざまな科学技術計算において重要である.DGEMM の高速化の手法の 1 つに Strassen のアルゴリズムがある.これは再帰的アルゴリズムであり,適用する回数を増やすことで計算量を O(N3) から O(Nlog7) まで削減することができる.しかし,計算機や行列サイズに合わせた適切な回数を選択しないと高速化できない.本研究では,Strassen のアルゴリズムを,自動チューニング機能付きの線形代数ラ …
NAID 110009536431