再帰のソースを表示
←
再帰
移動先:
案内
、
検索
あなたには「このページの編集」を行う権限がありません。理由は以下の通りです:
要求した操作を行うことは許可されていません。
このページのソースの閲覧やコピーができます。
'''再帰'''(さいき)とは、あるものについて記述する際に、記述しているものそれ自身への参照が、その記述中にあらわれることをいう。[[定義]]において、再帰があらわれているものを[[再帰的定義]]という。 主に[[英語]]のrecursionとその派生語の訳にあてられる。他にrecurrenceの訳([[回帰#物理学]]及び[[再帰性]]を参照のこと)や、reflectionの訳([[代名詞#再帰代名詞|再帰代名詞]]、[[再帰動詞]]。また、[[社会学]]で、対象に対する言及がその対象自体に影響を与えること([[:en:Reflexivity (social theory)]]))として「再帰」が使われることがある。[[数学的帰納法]]との原理的な共通性から、recursionの訳として[[数学]]では「[[帰納]]」を使うことがある。 == 再帰呼出し == '''再帰呼出し'''(さいきよびだし、[[英語|英]] recursive call)は、プログラミング技法の一つである。 手続きや関数といった概念をもつ[[プログラミング言語]]では、ある手続き中で再びその手続き自身を呼び出すことを認める場合が多い。これを'''再帰呼出し'''といい、[[階乗]]計算や[[フィボナッチ数列]]のように、本来再帰的な構造をもつ[[アルゴリズム]](再帰的アルゴリズム)を記述するのに適している。<!-- 再帰のことを[[帰納]]という場合もある。← 上と重複している。--> 再帰呼出しが実装されていない言語([[BASIC]]、[[FORTRAN]]など)では、プログラマが、スタックなどを利用して再帰と同様の効果をえられる。 複数の手続き/関数が互いに相手を呼ぶ場合も、広い意味での再帰呼出し([[相互再帰]])である。[[Pascal]] での例: <source lang="pascal"> procedure A; ... B ... end; procedure B; ... A ... end; </source> 処理を中断・終了する条件(下の例では引数 n の値が 0 である場合)が必ず一つは必要で、その部分が誤っていると、無限に関数を呼び出し続けることがある(→[[暴走]])。 再帰呼出しが正常に機能するためには、手続きが[[リエントラント]]である必要がある<!--[[副作用 (プログラム)|副作用]]を伴う手続型言語で再帰呼出しを可能にするためには、手続き/関数内部で用いられる変数(局所変数)及び戻り先を呼出しごとに保存しておく機構が必要であり、[[コールスタック]]が用いられることが多い-->。 === 再帰呼出しの例 === ここでは、階乗計算を例にとって各言語の再帰呼び出しのパターンを紹介する。 [[C言語]]での例: <source lang="c"> /* 階乗 n! を計算する */ int fact(int n) { if (n == 0) return 1; /* 脱出条件。0! は 1 である */ return fact(n - 1) * n; /* n! は (n-1)! に n を乗じたもの。再帰呼出し */ } </source> [[JavaScript]] ([[ECMAScript]]) での例: <source lang="javascript"> 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; }; </source> [[LISP|Lisp]]での例: <source lang="lisp"> ;;; 階乗 n! を計算する (defun fact (n) (or (and (zerop n) 1) ; 脱出条件。0! は 1 である (* n (fact (1- n))))) ; n! は (n-1) に n を乗じたもの。再帰呼出し </source> [[Visual Basic for Applications|VBA]]での例: <source lang="vb"> 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 </source> [[Pascal]]での例; <source lang="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; </source> [[Prolog]]での例; <source lang="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 を乗じたものである。 </source> == 類似した概念 == *[[帰納]] *[[回帰]] == 関連項目 == === 一般 === *[[再帰性]] *[[再帰的定義]] *[[相互再帰]] === 数学 === *[[数学的帰納法]] *[[再帰理論]] *[[帰納的集合]] *[[帰納的可算集合]] *[[帰納言語]] *[[帰納的可算言語]] *[[帰納的関数]] *[[原始再帰関数]] *[[漸化式]] === 計算機科学 === *[[末尾再帰]] *[[分割統治法]] *[[ネスティング]] *[[再帰下降構文解析]] *[[再帰データ型]] *[[ハノイの塔]] - プログラムの例題としてよく登場する。 *[[リカーシブスローダウン]] === 日常社会 === *[[再帰的頭字語]] === 文芸 === *落語『[[頭山]]』 ストーリーに再帰が現れる。 {{DEFAULTSORT:さいき}} [[Category:プログラミング|さいき]] [[Category:制御構造]] [[Category:数理論理学]] [[Category:計算理論]]
再帰
に戻る。
案内メニュー
個人用ツール
ログイン
名前空間
ページ
議論
変種
表示
閲覧
ソースを表示
履歴表示
その他
検索
案内
メインページ
コミュニティ・ポータル
最近の出来事
新しいページ
最近の更新
おまかせ表示
sandbox
commonsupload
ヘルプ
ヘルプ
井戸端
notice
bugreportspage
sitesupport
ウィキペディアに関するお問い合わせ
ツール
リンク元
関連ページの更新状況
特別ページ
ページ情報