ブログ「サイバー少年」

ブログ「サイバー少年」へようこそ!
小学六年生ごろからプログラミングを趣味にしている高校生のブログです。
勉強したことについての記事などを書いています。フリーソフトも制作、公開しています。
(当ブログについて詳しくは「ブログ概要紹介」を参照)

サイバー少年が作ったフリーソフトは「サイバー少年の作品展示場」へ

再帰はすげえ…けどループを使え!

超が付くほど久しぶりの記事投稿なため、記事を書く要領を忘れてしまいました(笑)

「なんかいつもと違うな」と感じる部分があるかも知れませんが、ご了承ください…。


以前、記事「再帰すげえ!」で、

ツリー構造を探索するときに、再帰を使えば直感的で分かりやすいプログラムを書ける、再帰すげえ!

というようなことを書きました。

しかし、“いげ太”さんのコメントによると、再帰で使うスタック領域はあまり大きくないそうで、スタックを食い潰してしまうこともあるそうです。

.NET Framework(というかCLR?)はスタックが1MBだそうですね。

ネイティブではないので関数のアドレスが32bitではないかも知れませんが、
32bitと仮定すれば、1MBで262143回の再帰が出来ることになります。

確かに、処理によっては262143回なんて食い潰してしまうでしょう。

しかも、これはローカル変数を一つも宣言しない場合の回数です。


まぁただ、.NETは基本的に配列までもがヒープに作られますから、再帰を使わなければ食い潰すこともないですもんね。

1MBでも余るわけですよ…。




と言う訳で、再帰を使うとスタックが食い潰されてしまうことがあるので、

ループでも書けるならループで書きたいなぁ、という結論になりました。

私はループで書けるものはループにしようと思います。

再帰で書いたやつは分かりやすいんですけどね~。



そこで、例の記事で書いた再帰のプログラムをスタックに書きなおしてみましたので公開いたします。

例の記事で書いたサンプル命題を解くわけですが、命題をもう一度、書いておきます。

再帰の素晴らしさを知るのにピッタリな命題として、自分で考えたやつです。


ここに1つの箱が置いてある。
その箱のなかには、さらにいくつかの箱が入ってあり、箱の色はそれぞれ異なる、カラフルな箱たちである。
箱のなかにいくつかの箱があって、そのなかにいくつかの箱があって…と続くが、永遠には続かない。
箱のなかの箱のなかの箱のなかの箱…を最後まで調べ、それぞれの箱の色をリスト形式で出力するプログラムを書け。



要するに、この命題にある箱はツリー構造になっています。

本当に、ツリー構造の探索は再帰が直感的ですからね。


以前は再帰を使ってパパパッとサンプルプログラムを書きましたが、今回はループを使います。

この程度なら、よほど箱が深い階層まで存在しない限り、再帰でもいいのですが、今回のテーマは「ループを使え!」です。

ループを使います。


…それで、ループを用いてのプログラムですが、再帰でパパパッと書いたときも考えてみたんですよ。

しかし、再帰ではすぐに書けたのに、ループではどうやって書けばいいのか分かりませんでした…。

本当に再帰の書きやすさはすげえんですよね。



さて、前置きが長かったですが、今回はなんとかループで書けたので、
(単なる自分の実力不足なのか!?)

以前と同じく、ColorBox型に、Color(string)フィールドと、InnerBoxes(ColorBox型の配列)フィールドが存在するという前提で、


ColorfulBox[] SearchBoxes (ColorBox rootbox) // メソッド
{

List<ColorBox> boxes = new List<ColorBox>(); // 見つかった箱のリスト

Stack<ColorBox> stackboxes = new Stack<ColorBox>(); // あとで探索する箱を溜めておくスタック
stackboxes.Push(rootbox); // 初期値として

while (stackboxes.Count > 0)
 {
 boxes.Add(stackboxes.Peek());
 foreach (ColorfulBox box in stackboxes.Pop().InnerBoxes)
  {
  stackboxes.Push(box);
  }
 }

return boxes.ToArray();
}


というコードです。
関数の引数等のインターフェースは以前と同じです。


やはり、なんか長いですし、何をしているのかよく分からない感じはあります。

ただ、このプログラムはスタックを用いています。

再帰で食い潰すほうのスタックではなく、データ構造としてのスタックです。

.NETのStackクラスはヒープ領域にインスタンスが作られますから、
どんなにプッシュしてもスタック領域が食い潰されることはありません。

スタック、スタックで訳わからないですね…。


やっぱり、わかりにくいプログラムですが、スタック領域のことを考えると、こんなプログラムじゃないといけないんですね。


難しいもんですよ。簡単さを取るかパフォーマンスを取るか。



ちなみに、このループで探索するプログラムをYahoo!ボックスにてアップしています。

Sample03.zip Yahoo!ボックス
http://yahoo.jp/box/SSSt9q

再帰バージョンも残してあり、

・再帰バージョン(以前のものから一部修正)
・ループ(スタック)バージョン
・ループ(キュー)バージョン

の三つの探索関数を収録しています。

命題も同じで、探索する箱のデータも同じ物です。
(CreateSampleBoxメソッドをコピーしただけ)


ループにはスタックとキューの二つのバージョンを入れてますが、スタックかキューかで順番が変わるのです。

再帰、スタック、キューのそれぞれの特徴が探索結果の順番に表れていて、なかなか面白いですよ。

今回は順番について言及しませんでしたが、順番についての記事も書きたいものです。



正直なところ再帰のほうが直感的でいいのですが、
パフォーマンスや安全性を問うと、こうするしかないようですね。

今回のループのプログラムは、すげえ複雑という訳ではないので、私はループをお奨めします。

再帰はすげえですけど…再帰はダメです。



いや~、それにしても記事を書くのが久しぶりで、力入れすぎて長文になりましたね。

これから記事を書く要領を思い出していけるといいです
(笑)

tag:

コメント

同じ意見です

再帰関数は確かに直感的ですね
つまり人間の試行にそっくりなんですよ
こうであればこうするという行為を繰り替えす関数ですからね
でもこれはあくまで人間の試行にそっくりなのでいろいろと不都合になるんですよ
たとえば、人間は随時例外をつくりだしたりできますが、パソコンは単調な作業を行う機械なのでそんなことはできません
簡単なアルゴリズムはなんともないのですが、複雑になると意外に時間は掛かるし予想外の動きをしてしまうことがあるので僕ももし初心者の方には勉強で学ぶぶんにはおすすめしますが普段から使うとなるとおすすめできません
ただこう言うと一切使わない人がでてきます
たとえば知人でgoto文を最悪の構文だからといって一回も使ったことがないという人がいました
まあいいものではないのかも知れませんが、時代によるプログラムを組み立てる考え方の変遷がわかるので、最悪だからといって学ぼうとはしないのはいいことではありません
再帰関数も同じくパソコンを直感で動かすという感覚は貴重なので「じゃあいらんか!」とは思わずに何回かは使って見たほうがいいです
使うのはループがわからないときか、あとはその関数の動きを10手先まで理解できるZEというぐらいにまでなったらいいと思います(3手先を読むだけで目が回りましたww


ちなみに僕も再び帰ってきたのでこれからもよろしくお願いします(再帰だけにww

  • 2013/05/30(木) 17:14:42 |
  • URL |
  • 刹那 #-
  • [ 編集 ]

Re: 同じ意見です

再帰の記事を書いたのはタイミング良かったかも知れませんね(笑)
刹那さんは高校生になったはずなので、進学おめでとうございます。

おっしゃるとおりで、再帰の書きやすさは素晴らしいんですよね。
ただ、スタック面でどうかと。

ツリーの階層が深くなると、それだけスタックは積まれることになりますからね。

ただ、直感的に書けることが売りで再帰は成り立っているわけです。
それが非常に重要なのですが…。

それで、再帰を使うべきかというのは言語にも大きく依存しますね。
関数の存在しない言語だってあるでしょうし。

言語特有のテクニックはありますね。

GoToも同じで、言語によります。
BASICなどはGoToによる制御が溢れています。

スタックを積まずに再帰する言語もあるかも知れないので、“言語に入っては言語に従え”という感じはあります。

末尾再帰

C# ではないんですけど、教養(?)として、「末尾再帰」とか知っておくとおもしろいかもしれませんね。

  • 2013/06/11(火) 12:28:59 |
  • URL |
  • @jsakamoto #mQop/nM.
  • [ 編集 ]

Re: 末尾再帰

私は記事を書く前に下調べを結構やっていたりするので、末尾再帰のことも知っていたりします。
上の刹那さんへのコメントで言った「言語に入っては言語に従え」も末尾再帰を意識していますね。
ブログ記事を書くと教養が身に付きますよ。

ところで、F#には末尾最適化があってC#にはないと聞くと、C#が劣っている感じがしますが、F#はループができないので(多分)、末尾最適化の機能を付けざるを得なかったわけですよね。

どうせ末尾再帰なら変数をスタックに積まないで良いわけで、C#でもループで簡単に再現できますからね。

// 1になるまで2で割るプログラム
int arg1 = (初期値); // 戻り値的なものもarg1
while(!(arg1 == 1)) {
arg1 /= 2;
}

コメントの投稿

トラックバック

トラックバック URL
http://cyberboy6.blog.fc2.com/tb.php/273-03a31fd7
この記事にトラックバックする(FC2ブログユーザー)

当ブログをご利用(閲覧等)になる場合は必ず「当ブログの利用規定」をお守りください。