再帰とは、 ある対象xの定義の中にxが登場するような物を言う。
→ 再帰
数学における再帰
- a1 = a2 = 1
- an+2 = an+1 + an
再帰的でない定義（一般解）は以下のような形になる。
この例から分かるように、再帰的定義を用いると、そうでない定義よりも直感的な定義をすることが可能になる場合がある。
プログラミングにおける再帰
プログラミングにおいて再帰は、関数や、データ型を定義する際に用いられる事が多い。
再帰関数
ある関数fの定義内にfの呼び出しが含まれるような関数のことを言う。関数型言語では多用される手法である。クイックソートのアルゴリズムは、再帰を用いて書くとすっきりと書くことができる。
例: nの階乗を求めるプログラム（C言語）
factの定義内にfactが登場しているので再帰的な関数の定義となっている。
int fact(int n) {
if(n <= 1)
return 1;
else
return n * fact(n-1);
}
再帰的データ型
あるデータ型Aの定義内にAを含むような型のことを言う。リストや、木は再帰的データ型の一例である。
例: 二分木構造 （OCaml）
'a treeの定義内に'a treeが登場しているので再帰的な型の定義となっている。
type 'a tree = Leef | Branch of 'a * 'a tree * 'a tree;;
関連項目
携帯版URL:
http://dic.nicomoba.jp/k/a/%E5%86%8D%E5%B8%B0
http://dic.nicomoba.jp/k/a/%E5%86%8D%E5%B8%B0
ページ番号: 459154
リビジョン番号: 58537
読み：サイキ
初版作成日: 08/08/13 20:13 ◆ 最終更新日: 08/08/16 09:43
編集内容についての説明/コメント: とりあえず詳細な記事。「再帰」は一般用語じゃないから説明が必要だと思う
記事編集 / 編集履歴を閲覧 / Twitterで紹介
JASRAC許諾番号: 9011622001Y31015
ヘッダー：固定
ヘッダー：追従