「再帰」の版間の差分
タグ: 取り消し |
2402:6B00:5609:EF00:91D:F13B:73AD:DFAB (会話) による ID:71092176 の版を取り消し タグ: 取り消し |
||
3行目: | 3行目: | ||
主に[[英語]]のrecursionとその派生語の訳にあてられる。他にrecurrenceの訳([[回帰#物理学]]及び[[再帰性]]を参照のこと)や、reflexiveの訳<ref>[[代名詞#再帰代名詞|再帰代名詞]]、[[再帰動詞]]。また、[[社会学]]で、対象に対する言及がその対象自体に影響を与えること。[[:en:Reflexivity (social theory)]]も参照。</ref>として「再帰」が使われることがある。[[数学的帰納法]]との原理的な共通性から、recursionの訳として[[数学]]では「[[帰納]]」を使うことがある。 |
主に[[英語]]のrecursionとその派生語の訳にあてられる。他にrecurrenceの訳([[回帰#物理学]]及び[[再帰性]]を参照のこと)や、reflexiveの訳<ref>[[代名詞#再帰代名詞|再帰代名詞]]、[[再帰動詞]]。また、[[社会学]]で、対象に対する言及がその対象自体に影響を与えること。[[:en:Reflexivity (social theory)]]も参照。</ref>として「再帰」が使われることがある。[[数学的帰納法]]との原理的な共通性から、recursionの訳として[[数学]]では「[[帰納]]」を使うことがある。 |
||
===Googleでの検索=== |
|||
Googleで再帰、またはRecursionと検索すると[[もしかして:再帰]]や[[もしかして:Recursion]]と押してもずっと表示されるイースターエッグがある。 |
|||
== 再帰呼出し == |
== 再帰呼出し == |
||
116行目: | 120行目: | ||
== 関連項目 == |
== 関連項目 == |
||
{{関連項目過剰|date=2018年12月|section=1}} |
|||
=== 一般 === |
=== 一般 === |
||
*[[再帰性]] |
*[[再帰性]] |
2018年12月27日 (木) 09:41時点における版
再帰(さいき)は、あるものについて記述する際に、記述しているものそれ自身への参照が、その記述中にあらわれることをいう。定義において、再帰があらわれているものを再帰的定義という。自己相似の記事も参照のこと。
主に英語のrecursionとその派生語の訳にあてられる。他にrecurrenceの訳(回帰#物理学及び再帰性を参照のこと)や、reflexiveの訳[1]として「再帰」が使われることがある。数学的帰納法との原理的な共通性から、recursionの訳として数学では「帰納」を使うことがある。
Googleでの検索
Googleで再帰、またはRecursionと検索するともしかして:再帰やもしかして: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 を乗じたもの。再帰呼出し */
}
自身を呼び出す手法なので、引数が同じ値のままとなって再帰終了条件を満たさないというような状況にならないよう、値の変化に注意する必要がある。
再帰的データ構造
連結リストや木構造は、要素(ノード)の型の中にその要素型自身への参照(自己参照)が存在するようなデータ型を用いて実現される。これは再帰的データ構造(再帰データ型)である。再帰的データ構造の探索には、再帰呼び出しを使うことが多い。
類似した概念
関連項目
一般
数学
計算機科学
日常社会
文芸
- 落語『頭山』 ストーリーに再帰が現れる。
脚注
- ^ 再帰代名詞、再帰動詞。また、社会学で、対象に対する言及がその対象自体に影響を与えること。en:Reflexivity (social theory)も参照。