再帰単語

サイキ

  • 4
  • 0
掲示板をみる(31)
  • twitter
  • facebook
  • はてな
  • LINE
  • ほめる(4)
  •  
  •  
  •  
  •  
  • その他

再帰とは、 ある対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回の手順が必要になることになる。

関連項目

この記事を編集する

掲示板

  • 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のときだけこう、というに考えるのが再帰流。

おすすめトレンド

急上昇ワード改

最終更新:2020/09/29(火) 19:00

ほめられた記事

最終更新:2020/09/29(火) 19:00

ウォッチリストに追加しました!

すでにウォッチリストに
入っています。

OK

追加に失敗しました。

OK

追加にはログインが必要です。

           

ほめた!

すでにほめています。

すでにほめています。

ほめるを取消しました。

OK

ほめるに失敗しました。

OK

ほめるの取消しに失敗しました。

OK

ほめるにはログインが必要です。

タグ編集にはログインが必要です。

タグ編集には利用規約の同意が必要です。

TOP