再帰単語

サイキ

再帰とは、 ある対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;;

再帰的解法

ハノイの塔
T1 T2 T3
ハノイの塔a ハノイの塔b ハノイの塔c

再帰的な手法を使い、問題を解く手順である。有名なものにハノイの塔がある。図で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回の手順が必要になることになる。

関連項目

【スポンサーリンク】

スマホ版URL:
https://dic.nicovideo.jp/t/a/%E5%86%8D%E5%B8%B0

この記事の掲示板に最近描かれたお絵カキコ

この記事の掲示板に最近投稿されたピコカキコ

ピコカキコがありません

再帰

20 ななしのよっしん
2014/08/10(日) 05:58:27 ID: z1sr7zxxHH
>>15
……google先生って、お茶ですねえ(笑)



再帰的処理っていうのはかなり本質から外れた概念で、
元々あったのは「再帰的定義」とか「再帰アルゴリズム」なのね(概念自体は電算機ができる前から普通にあった)
宣言では必然的に出てくるので、言仕様レベル親和性を持たせるようにしてる。
Cとかの手続き型言語でこれをやるのは、ぶっちゃけしこしこforループに変換するのが手続き型言語の本来あるべき姿
21 ななしのよっしん
2015/07/18(土) 16:45:53 ID: 0wG5IHxD9Z
再帰的でないものはプログラミングできないのならすべてのプログラム再帰で表せる・・・?
22 ななしのよっしん
2016/04/24(日) 13:14:54 ID: +uIYsH4hqK
階乗って再帰の説明で必ずと言っていいほど見かけるけど、
forループを使う方がわかりやすくて再帰のありがたみを感じない・・・
23 ななしのよっしん
2017/04/30(日) 01:52:03 ID: pmNjB3uhju
ぷよぷよとかマインスイーパーとかの盤面の消去判定でうまく活用できる
同じ条件を満たす限り自動で繰り返すのが重要
階乗の繰り返し数nをいちいちめ用意する必要がない
あるいはnに相当するものをめるのが困難な場合に有効
24 ななしのよっしん
2017/10/22(日) 00:15:33 ID: f+5O+t2nD3
1番素数を2とすると、
2番素数は3となり、
3番素数は5となり、
5番素数は11となり、
11番素数31となり、
31素数127となり、
127素数709となり、
709番素数5381となり、
5381番素数52711となり、
52711番素数648391となり、・・・
25 ななしのよっしん
2017/12/07(木) 10:24:54 ID: X2Dn9hE4jU
>>21
包含関係を勉強するといい
再帰的な振る舞いをする処理はプログラムに含まれているが、プログラム自体が再帰的なわけじゃない

わざわざ再帰的な表現にするのは直感的にわかりやすくなるメリットがあるわけで、そうでもないなら本末転倒も甚だしい
いずれにせよCだったらfor文使ったほうが読みやすくてスマートだわ
26 ななしのよっしん
2018/02/09(金) 00:35:41 ID: SRCS0+jJ6+
代表的なのはクイックソートだな。ループでも書けるが考え方としては不自然になる。
27 ななしのよっしん
2018/02/24(土) 22:38:58 ID: RIZcKPLppZ
あんまり何も考えずに使うと計算がすごい時間かかるときもあるんよね
確かフィボナッチ数列を愚直に再帰めるプログラムの例とかすごい時間かかるっての見たことある
でも、末尾再帰最適化とかで計算が増えるのを防げる場合もある。
28 ななしのよっしん
2018/12/27(木) 00:49:17 ID: brUYitsHqM
>>18 差別義者差別
29 ななしのよっしん
2019/02/21(木) 22:52:43 ID: bf8DLXL5Sj
再帰が実用的に有効な場合ってほとんどくない?
何かあったらか教えてください