再帰 再帰の概要

再帰

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2015/01/13 15:29 UTC 版)

主に英語のrecursionとその派生語の訳にあてられる。他にrecurrenceの訳(回帰#物理学及び再帰性を参照のこと)や、reflectionの訳(再帰代名詞再帰動詞。また、社会学で、対象に対する言及がその対象自体に影響を与えること(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 を乗じたものである。

類似した概念




「再帰」の続きの解説一覧





固有名詞の分類


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

再帰に関係した商品

辞書ショートカット

カテゴリ一覧

全て

ビジネス

業界用語

コンピュータ

電車

自動車・バイク

工学

建築・不動産

学問

文化

生活

ヘルスケア

趣味

スポーツ

生物

食品

人名

方言

辞書・百科事典

すべての辞書の索引

「再帰」の関連用語

再帰のお隣キーワード

   

英語⇒日本語
日本語⇒英語
   
検索ランキング

画像から探す

マダムバタフライ

ピーシング針

骨材露出工法

字牌

屋久島宮之浦岳流水

アトサヌプリ

821P

Alligator Wisdom





再帰のページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

  
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの再帰 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2015 Weblio RSS