読者です 読者をやめる 読者になる 読者になる

微妙にあきらめてた人のための再帰入門1

皆さん、再帰してますか?!
プログラミング言語ニューウェーブを語る上で欠かせない技法となっている再帰
昔っからあるんだけどいまいち使ってない、とかって人も多いんじゃないんでしょうか

でも再帰をしってるかしってないかでかけるコードにぐっと差が広がりますよ!

まず、再帰に対するよくある偏見について弁解しときましょう

再帰は遅い
そんなことないよ!あとでkwsk説明するけどそんなことないよ!

再帰って複雑
そんなことないよ!むしろほとんどの場合ループより簡単にかけるよ!


ってわけでまず、再帰ってなんだろう?
よくあるフィボナッチ数列を求めるプログラムとかで説明してみるね

フィボナッチ数列って何ってひとはここをみといてね!
http://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%9C%E3%83%8A%E3%83%83%E3%83%81%E6%95%B0

ふつうにループをつかうとこんなかんじ、

def fib n
  return 0 if n == 0
  return 1 if n == 1

  value = nil, f2 = 0, f1 = 1
  (n-1).times do |n|
    value = f1 + f2;
    f2 = f1;
    f1 = value;
  end
  value
end

言語はRubyをつかってるよ!
とっても素直にかいてあってわかりやすいね。
でももっとシンプルにかけたりするんだ
こんなかんじ

def fib n
  if n == 0
    0
  elsif n == 1
    1
  else
    fib(n-1) + fib(n-2)
  end
end

みじか!ところでこれ、fibのなかでfibを呼び出してるよね
こうやって自分自身を呼び出すことを再帰っていうんだ(厳密にはちょっと違うかも)
で、何回も呼び出されるうちにだんだんnが小さくなっていってn==0かn==1になるともどってくる

さっきのWikipediaのリンクを見てもらうとわかるけど、再帰を使うと数学の定義そっくりなかきかたになるよね!それもそのはず、フィボナッチ数列の数学の定義が再帰を使ってるからなんだ!

あと変数とか全然ないよね、ふつう再帰を使うと変数が減って、プログラムがコードが短くなるんだ。再帰になれちゃうとアルゴリズムっぽいコードを書く時に変数がいっぱい出てくるとちょっと「うげっ」てなる




眠くなったので今日はこの辺で、続きはあした




以下あんまり再帰と関係ないこと!

ruby フィボナッチ数列」でぐぐるid:CnaI くんのページがでてくるね。すごい!
http://d.hatena.ne.jp/CanI/20090807/1249657492