再帰とは、 ある対象xの定義の中にxが登場するような物を言う。
→ 再帰
再帰的でない定義(一般解)は以下のような形になる。
この例から分かるように、再帰的定義を用いると、そうでない定義よりも直感的な定義をすることが可能になる場合がある。
プログラミングにおいて再帰は、関数や、データ型を定義する際に用いられる事が多い。
ある関数fの定義内にfの呼び出しが含まれるような関数のことを言う。関数型言語では多用される手法である。クイックソートのアルゴリズムは、再帰を用いて書くとすっきりと書くことができる。
factの定義内にfactが登場しているので再帰的な関数の定義となっている。
int fact(int n) {
if(n <= 1)
return 1;
else
return n * fact(n-1);
}
あるデータ型Aの定義内にAを含むような型のことを言う。リストや、木は再帰的データ型の一例である。
'a treeの定義内に'a treeが登場しているので再帰的な型の定義となっている。
type 'a tree = Leef | Branch of 'a * 'a tree * 'a tree;;
T1 | T2 | T3 |
![]() |
![]() |
![]() |
再帰的な手法を使い、問題を解く手順である。有名なものにハノイの塔がある。図でn個のブロックを他の塔に移動するのだが、このとき「ブロックは三本の塔のうちどれかに置ける」「ブロックはひとつずつしか動かせない」「小さいブロックの上に大きなブロックを乗せてはならない」と言う制約条件がある。
これは再帰的に考えれば簡単である。つまり、n個(n>1)のブロックをTxからTyに動かしたいのならn-1個のブロックをTxからT(6-x-y)に動かし、n番目のブロックをTxからTyに動かし、n-1個のブロックを改めてT(6-x-y)からTyに動かすのである。n=1なら普通に1回で動かせる。
つまり、n個のブロックを動かす手順数はn>1なら「n-1個のブロックを動かす手順数*2+1回」であり、n=1なら1回の手順が必要なので一般にn個動かすには2n-1回の手順が必要になることになる。
掲示板
29 ななしのよっしん
2019/02/21(木) 22:52:43 ID: bf8DLXL5Sj
再帰が実用的に有効な場合ってほとんど無くない?
何かあったら誰か教えてください
30 ななしのよっしん
2019/09/20(金) 01:06:28 ID: CWgXWlqKb0
というより一般的には使うところがあまりないかな
コンパイラー書くなら使うけど、コンパイラー書くってのは普通はやらないもんね
31 ななしのよっしん
2020/03/27(金) 23:57:45 ID: SRCS0+jJ6+
手続き型だとforとかの方が自然だから再帰にするメリットはあんまりないと思う。
でも逆に関数型だと再帰のほうが書きやすんだよね。むしろループは書きたくない。
なんでかというと、関数型のコードは過程じゃなくて定義の組み合わせで書くから、自分の定義がすでにあるものとしてエッジケースだけ特殊化する方がわかりやすい。一般論としてnはこう、0のときだけこう、という風に考えるのが再帰流。
急上昇ワード改
最終更新:2025/06/15(日) 04:00
最終更新:2025/06/15(日) 04:00
ウォッチリストに追加しました!
すでにウォッチリストに
入っています。
追加に失敗しました。
ほめた!
ほめるを取消しました。
ほめるに失敗しました。
ほめるの取消しに失敗しました。