ブログ「サイバー少年」

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

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

再帰すげえ!

再帰呼び出しってすげえです!

…いや、なんで急にこんなこと言いだすのかと言うと、
私は今まで、再帰の有用性をあまり感じたことがなかったんですよ。

だって、ループで代用できなくはないですし、あと、私自身よく分からない話ですが、
再帰にしてしまうとループよりも、スタック領域にデータをたくさん積んでしまうんじゃないかな、と思っているわけです。

まぁ、高性能なパソコン上のプログラムですから、積んでも積まなくてもいいと思いますが…。

しかし、やはり無駄だなぁと思って、普段はループを使っていたわけです。


しかし、気づきました!

パフォーマンス面は劣るかもしれないですが、
再帰のほうが直感的に書けるような命題が、世の中にはいっぱいあります。



こんな感じの思考をしている間に、
“再帰のほうが直感的に書ける命題”というものを、1つ考えてみました。

オリジナルです。


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



箱ばっかりで訳が分からなくなってきますが、
この命題は再帰の凄さが、とても実感できるんですよ。


自分でプログラムを考えてみて、まずループでの方法を考えてみたんですが、訳が分からなくなって挫折しました。

そこで再帰を使ってみたら、なんと書きやすいことか!



さて、C#ですがコードを載せます。

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


string[] SearchBoxes(ColorBox rootbox) { // メソッド宣言

List<string> colorlist = new List<string>();

foreach(ColorBox box in ColorBoxes)
{
colorlist.Add(box.Color);
colorlist.AddRange(SearchBoxes(box)); // 再帰!
}

}



これで!引数のrootboxに要素を設定すれば!
これだけで!いけるのです!

ループを使う方法じゃ、訳が分からなくなったのに対して、
再帰はこれだけでいけるのですよ!


再帰恐ろしいです。再帰すげえです。

ところで、この命題は「使うか?」と言いたくなる命題ですが、

例えば、Formコントロールに、さらにコンテナが配置されてあったとして、コンテナ内を含む全てのコントロールを探索するときも使いますよね。

同じようなものです。この例も再帰では分かりやすいです。



ところで、この命題にそって出力するプログラムを作りました。

この記事では、再帰するメソッドの部分しか書かなかったので、ColorBox型とかよく分からなかったと思います。

そこで、一連のプログラムをEXEファイル付きでダウンロード出来ます。

Yahoo!ボックス
http://yahoo.jp/box/90VdO3

箱のデータをXMLから読めるようにしようかなとも思いましたが、いろいろと面倒くさそうだったので、
ソースコード中にCreateSampleBoxメソッドとして直接、配列で書いています。

詳細は説明しないので、ソースコードを読んでみてください。



いや~、再帰をなめていましたが、場合によっては凄い力を発揮しますよ。

パフォーマンス面ではループより劣るかも知れませんが…。

まぁ、パソコンはメモリ山盛りですから、大丈夫なんでしょうね。

再帰すげえです。見直しました。再帰万歳!

tag:

コメント

再起呼び出しで、
一番、有名なのは、フォルダ構造かな。
あとは、サイトマップの作成とか。。。

Tree構造なものには、全て使われていますね。
理解できない場合だと、3階層までとか、
条件付のものができあがってしまって、
あとで、困る事が多いです(笑)

  • 2013/04/15(月) 18:56:30 |
  • URL |
  • 通りすがり #EBUSheBA
  • [ 編集 ]

Re: 通りすがり

なるほど~!
やっぱりツリーに最適なんですね。
確かにフォルダ探索にはピッタリですよね。
再帰も重要なテクニックだとあらためて感じました。

再帰と聞いて。

なんか、挙げられてるコード、間違ってるような。ニュアンスは伝わりますが。まず return がないのと、ColorBoxes って未定義の変数が使われているのと。
# すいません、Yahoo!ボックスの方は、見てませんです。

で、提示された問題だと、一番最初に引数に与えた rootbox の色も取った方がよいかと思えますので、こんな感じとか。

List<string> SearchBoxes(ColorBox rootbox)
{
var colorlist = new List<string>();
colorlist.Add(rootbox.Color);
foreach (var box in rootbox.InnerBoxes) {
colorlist.AddRange(SearchBoxes(box));
}
return colorlist;
}

さらに言うと、入れ子構造になっているのは ColorBox の方なので、色のリストではなくて箱のリストを返す方が、なんとなく素直な実装の気がします。というわけで、ざっくりですが、僕ならこんな感じで書くかなあと。

public class ColorBox
{
public string Color { get; set; }
public List<ColorBox> InnerBoxes { get; set; }

public ColorBox() : this("White")
{ }

public ColorBox(string color)
{
this.Color = color;
this.InnerBoxes = new List<ColorBox>();
}

private void ListAllBoxesImpl(List<ColorBox> result)
{
result.Add(this);
foreach (var box in this.InnerBoxes) {
box.ListAllBoxesImpl(result);
}
}

public List<ColorBox> ListAllBoxes()
{
var boxs = new List<ColorBox>();
this.ListAllBoxesImpl(boxs);
return boxs;
}
}

class Program
{
static void Main(string[] args)
{
// ColorBox rootbox = ...;

foreach (var box in rootbox.ListAllBoxes())
Console.WriteLine(box.Color);
}
}

> まぁ、パソコンはメモリ山盛りですから、大丈夫なんでしょうね。
それがそうもいかないです。言われるように、再帰を行うとスタック領域をたくさん使うことになるのですが、このスタック サイズ、.NET ではデフォルトで 1MB です。これを食いつぶすと StackOverflowException の例外となります(たくさん使えるメモリは、ヒープ領域の方ですね)。

再帰は強力ですが、用法容量を守って正しくお使いください。

  • 2013/04/17(水) 22:39:16 |
  • URL |
  • いげ太 #-
  • [ 編集 ]

パフォーマンス…スタック領域…
自分はあるトラウマのお陰で重い命令は使わなくなってしまったw
例 getpixel → lockbits

使用もほどほどに…

  • 2013/04/18(木) 01:24:30 |
  • URL |
  • まっちゃ #TYxE//as
  • [ 編集 ]

Re: いげ太

いげ太さんお久しぶりです。

そうですね。returnを忘れていました…(笑)
IDEを使わずに直接、書いていましたからね。メソッドの最後に
return colorlist.ToArray(); を付けてください。

あとColorBoxesの件も、最初はColorBoxesという変数を作っていたものですから、書き換えるのを忘れていました。
あそこは rootbox.InnerBoxes だったということにしてください。

うっかり変なコード書いちゃって申し訳ないです。普段はVisual Studioが怒ってくれますからね…。

それと、サンプルコードありがとうございます。
全く思いつかなかったやり方で、勉強になります。

ご指摘の戻り値の件は、記事内では分かりやすいようにstring[]にしていますが、Yahoo!ボックス上のやつでは箱のリストを返しているんですよ~。


最後に、スタック領域の件については驚きです。今のパソコンでも安全ではないんですね。

Re: まっちゃ

以前、よく言ってましたね。LockBitsは。
GetPixelは楽ですけどね。

Stackクラスで擬似再帰を作れるのかも。

コメントの投稿

トラックバック

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

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