2011年07月26日
アプリケーションの設定情報の扱いについて考えてみる(4)
「アプリケーションの設定情報の扱いについて考えてみる」の4回目です。
■ ApplicationScopedSettingAttribute
[UserScopedSetting] の代わりに、[ApplicationScopedSetting]属性を付加すると、 ユーザ単位ではなく、
アプリケーションでひとつの(つまり、すべてのユーザーに対して共通の) 値を持つことができます。
しかし、この属性を付けた場合は、デフォルトの動作(LocalFileSettingsProviderの動作)では、読み取り専用となります。
値を変更し保存することができません。
この読み取り専用の設定情報は、app.config に記述することになります。
以下に、その例を示します。
なお、これを書きこみ可能とするには、System.Configuration.SettingsProvider を継承した独自のプロバイダークラスを
作成する必要がありますが、この作成方法については、省略します。
興味あるかたは、MSDN等で調べてください。
■ ApplicationScopedSettingAttribute
[UserScopedSetting] の代わりに、[ApplicationScopedSetting]属性を付加すると、 ユーザ単位ではなく、
アプリケーションでひとつの(つまり、すべてのユーザーに対して共通の) 値を持つことができます。
しかし、この属性を付けた場合は、デフォルトの動作(LocalFileSettingsProviderの動作)では、読み取り専用となります。
値を変更し保存することができません。
この読み取り専用の設定情報は、app.config に記述することになります。
以下に、その例を示します。
なお、これを書きこみ可能とするには、System.Configuration.SettingsProvider を継承した独自のプロバイダークラスを
作成する必要がありますが、この作成方法については、省略します。
興味あるかたは、MSDN等で調べてください。
2011年07月24日
アプリケーションの設定情報の扱いについて考えてみる(3)
「アプリケーションの設定情報の扱いについて考えてみる」 の3回目です。
■ バージョンアップ時に前バージョンの情報を引き継ぐ
アセンブリのバージョンが上がったときは、configファイルの保存場所が変更されることは前回説明しました。
これは何を意味するかというと、そのままでは、前バージョンの設定情報を取得することができないということです。
Windowsのサイズと位置程度ならば、初期状態に戻ってしまってもかまわないかもしれませんが、設定情報を引き継ぎたいということは、良くあることです。
この目的のために、ApplicationSettingsBase には、Upgradeというメソッドが用意されています。
しかし、何を基準にUpgradeを呼び出したら良いのかを判断する方法が用意されていないようです。
※ 調べましたが、見つけることができませんでした。
そのため、自前でバージョンが変更されたかどうかを判断するコードを書く必要があります。
ここでは、IsUpgraded というプロパティを WindowInfoに追加することで対応します。
このプロパティを使った、設定情報の読み込みを以下に示します。
これで、設定情報の引継ぎが可能になります。
2011/8/9 追記
IsUpgradedプロパティのコードが間違っていましたので、訂正しました。
■ バージョンアップ時に前バージョンの情報を引き継ぐ
アセンブリのバージョンが上がったときは、configファイルの保存場所が変更されることは前回説明しました。
これは何を意味するかというと、そのままでは、前バージョンの設定情報を取得することができないということです。
Windowsのサイズと位置程度ならば、初期状態に戻ってしまってもかまわないかもしれませんが、設定情報を引き継ぎたいということは、良くあることです。
この目的のために、ApplicationSettingsBase には、Upgradeというメソッドが用意されています。
しかし、何を基準にUpgradeを呼び出したら良いのかを判断する方法が用意されていないようです。
※ 調べましたが、見つけることができませんでした。
そのため、自前でバージョンが変更されたかどうかを判断するコードを書く必要があります。
ここでは、IsUpgraded というプロパティを WindowInfoに追加することで対応します。
このプロパティを使った、設定情報の読み込みを以下に示します。
これで、設定情報の引継ぎが可能になります。
2011/8/9 追記
IsUpgradedプロパティのコードが間違っていましたので、訂正しました。
2011年07月20日
メールマガジン 「正規表現編」の次は何をやろうか?
メールマガジン「C#プログラミングレッスン」、今は「正規表現編」を連載しているのですが、
来週の発行で、「正規表現編」も終了の予定です。
ということで、次の話題を考えないといけないのですが、まだ、次に何を書くか決まってません。
毎回のことなのですが、いったい、次に何をやったらいいんでしょうか。
新たにC#を始める人はたくさんいるわけだし、そういった人を対象に記事を書きべきなのか
しかし、すでに2000名の読者の方がいるわけだから、その人たちにも読んでもらえるものじゃないといけないし...
純粋にC#の機能にまとを絞った記事を書くのは、ほぼ書き尽くした感があるので、もう無理かなーと思っている。
(Geekな人たちからは、いやまだまだあるぞと言われそうですが...)
.NET Frameowkrのベースクラスライブラリについても、基礎的なのはすでに説明しているし。
何かリクエストがあればお願いします。
ところで、次回で、とうとうメルマガも300号です。
300号を記念して、プレゼントを用意しました。
詳細は、来週発行のメルマガでお知らせします。
来週の発行で、「正規表現編」も終了の予定です。
ということで、次の話題を考えないといけないのですが、まだ、次に何を書くか決まってません。
毎回のことなのですが、いったい、次に何をやったらいいんでしょうか。
新たにC#を始める人はたくさんいるわけだし、そういった人を対象に記事を書きべきなのか
しかし、すでに2000名の読者の方がいるわけだから、その人たちにも読んでもらえるものじゃないといけないし...
純粋にC#の機能にまとを絞った記事を書くのは、ほぼ書き尽くした感があるので、もう無理かなーと思っている。
(Geekな人たちからは、いやまだまだあるぞと言われそうですが...)
.NET Frameowkrのベースクラスライブラリについても、基礎的なのはすでに説明しているし。
何かリクエストがあればお願いします。
ところで、次回で、とうとうメルマガも300号です。
300号を記念して、プレゼントを用意しました。
詳細は、来週発行のメルマガでお知らせします。
2011年07月18日
アプリケーションの設定情報の扱いについて考えてみる(2)
前回の続き
前回は、ApplicationSettingsBase クラスを継承した簡単なクラス定義例をお見せしました。
今回は、「デフォルト値の設定」と「保存場所とその形式」について簡単に解説します。
■ デフォルト値を設定する。
デフォルト値を設定するには、NullReferenceException 例外をキャッチし、そこで、値を設定する方法と、
属性でデフォルト値を設定する方法の2通りがあります。
属性でデフォルト値を設定するには、DefaultSettingValueAttribute 属性を指定します。
前回示したWindowInfoクラスを例に、そのコードを示します。
このようにすれば、設定ファイルが存在しない場合にも例外は発生しませんので、try-catchは不要になります。
■どこに保存されるのか
exeファイルが存在するフォルダをみても、それらしいファイルは存在していません。
では、どこに保存されているのかというと、Windows7では、
といった場所に保存されます。
アセンブリにCompanyNameが設定されていない場合は、exe名が CompanyNameになります。
1.0.0.0 は、アセンブリのバージョンを示します。
製品バージョンやファイルバージョンではなく、アセンブリのバージョンです。
アセンブリのバージョンが変わると、保存場所も変わります。
ビルド番号やリビジョン番号が変わっても保存場所は変わります。
■ 構成ファイルの形式
構成ファイルのサンプルを示します。
前回は、ApplicationSettingsBase クラスを継承した簡単なクラス定義例をお見せしました。
今回は、「デフォルト値の設定」と「保存場所とその形式」について簡単に解説します。
■ デフォルト値を設定する。
デフォルト値を設定するには、NullReferenceException 例外をキャッチし、そこで、値を設定する方法と、
属性でデフォルト値を設定する方法の2通りがあります。
属性でデフォルト値を設定するには、DefaultSettingValueAttribute 属性を指定します。
前回示したWindowInfoクラスを例に、そのコードを示します。
このようにすれば、設定ファイルが存在しない場合にも例外は発生しませんので、try-catchは不要になります。
■どこに保存されるのか
exeファイルが存在するフォルダをみても、それらしいファイルは存在していません。
では、どこに保存されているのかというと、Windows7では、
といった場所に保存されます。
アセンブリにCompanyNameが設定されていない場合は、exe名が CompanyNameになります。
1.0.0.0 は、アセンブリのバージョンを示します。
製品バージョンやファイルバージョンではなく、アセンブリのバージョンです。
アセンブリのバージョンが変わると、保存場所も変わります。
ビルド番号やリビジョン番号が変わっても保存場所は変わります。
■ 構成ファイルの形式
構成ファイルのサンプルを示します。
部分和問題を動的計画法で解く
部分和問題とは、
「与えられた n 個の整数(集合A)と 整数 X があった時に、集合Aから任意の数の整数を選び、
その数の和(部分和)が、X に等しくなるような、部分集合を求める」 というものです。
たとえば、 [3,7,8,12,13,18] の部分和が 27 になる部分集合は、[7,8,12] となります。
このような問題を解くには、バックトラックでも解くことは可能ですが、要素の数が多くなると
組合せの数が増えすぎて、対応できなくなることもあり得ます。
このような時に利用するのが、動的計画法です。
僕のWebサイト「Gushwell's C# Programming Page」に、この部分和問題を解くプログラムコードを掲載しました。
興味のある方はどうぞ。
「与えられた n 個の整数(集合A)と 整数 X があった時に、集合Aから任意の数の整数を選び、
その数の和(部分和)が、X に等しくなるような、部分集合を求める」 というものです。
たとえば、 [3,7,8,12,13,18] の部分和が 27 になる部分集合は、[7,8,12] となります。
このような問題を解くには、バックトラックでも解くことは可能ですが、要素の数が多くなると
組合せの数が増えすぎて、対応できなくなることもあり得ます。
このような時に利用するのが、動的計画法です。
僕のWebサイト「Gushwell's C# Programming Page」に、この部分和問題を解くプログラムコードを掲載しました。
興味のある方はどうぞ。
2011年07月10日
アプリケーションの設定情報の扱いについて考えてみる(1)
■はじめに
アプリケーション独自の設定情報を扱いたい、そんな要求に答えるには、太古の昔は、INIファイルが定番でしたが、
いつしか、レジストリが主流になり、そして.NETでは、XML形式のconfigファイルへと移ってきました。
configファイルにアプリケーション独自の情報を設定するのに、もっとも手軽なのが、App.config の
要素を使う方法です。
ただ、これは、
・全てを文字列として扱う必要がある。
・項目を一つ一つ指定してアクセスする必要がある
など、柔軟性に欠ける部分があります。
そして、さらに問題となるのが、書き込みをしたいという要求にうまく対応できないということです。
そこで、数回にわけて、設定ファイルの読み書きについて考えてみます。
まずは、.NET Frameworkでそのために用意されていると思われるApplicationSettingsBaseクラス を使い、
アプリケーション独自の設定情報の読み書きについて考えてみます。
■ApplicationSettingsBaseクラスを利用した設定ファイルの読み書き
例えば、ウインドウのサイズと位置を保存しておきたいとしましょう。
当然、これらの値はひとつのクラスとして扱いたいですね。
例えば、
というクラスを考えてみます。
このクラスを 設定ファイルに保存できるようにするには、ApplicationSettingsBase から継承し、
以下のように書き換えてやる必要があります。
随分コードが増えてしまいましたが、パターン化されていますので、 機械的にコーディングできると思います。
このクラス定義ができれば、あとは読み書きのコードを書くだけです。
読み込みは、WindowInfo のオブジェクトを生成し、プロパティにアクセスするだけです。
なお、このプログラムを最初に起動した場合は、値を読み込むことが出来ないために、
NullReferenceException 例外が発生します。この例外が出たときには、何もせずにデザイン時の値を
そのまま使います。
書き込みは、WindowsInfoの各プロパティに値を設定し、Saveメソッドを呼び出します。
なお、WindowsFormsでは、フォームデザイナーのプロパティ画面で、(ApplicationSettings) で
保存したいプロパティを設定すれば、いちいち上記のようなコードを書く必要はありません。
あくまでも、サンプルとして見てください。
実際、自動生成される Settings.Designer.cs を見てみると、ApplicationSettingsBase クラスを継承したクラスが
定義されています。
もちろん、フォームやGUIコントロールのプロパティ以外の値を設定するには、デザイナーでのサポートは
ありませんので、ApplicationSettingsBaseクラスを利用するなら、ここに書いた方法で値を設定することになります。
(続く...)
追記 (2011/07/11)
最後の文は、ちょっと語弊がある文章でした。
C#プロジェクトの Properties フォルダの、Settings.settingsを開いて表示されるデザイナー(これもデザイナー
の一種ですね)で独自の情報を格納することができます。
ただ、このシリーズでは、Settings.settingsを開いて表示される設定デザイナーを利用する方法については、割愛します。
ApplicationSettingsBase を直接使ってみることで、Settings.settingsで作成する 設定ファイルクラスを
より理解できるようになります。
アプリケーション独自の設定情報を扱いたい、そんな要求に答えるには、太古の昔は、INIファイルが定番でしたが、
いつしか、レジストリが主流になり、そして.NETでは、XML形式のconfigファイルへと移ってきました。
configファイルにアプリケーション独自の情報を設定するのに、もっとも手軽なのが、App.config の
ただ、これは、
・全てを文字列として扱う必要がある。
・項目を一つ一つ指定してアクセスする必要がある
など、柔軟性に欠ける部分があります。
そして、さらに問題となるのが、書き込みをしたいという要求にうまく対応できないということです。
そこで、数回にわけて、設定ファイルの読み書きについて考えてみます。
まずは、.NET Frameworkでそのために用意されていると思われるApplicationSettingsBaseクラス を使い、
アプリケーション独自の設定情報の読み書きについて考えてみます。
■ApplicationSettingsBaseクラスを利用した設定ファイルの読み書き
例えば、ウインドウのサイズと位置を保存しておきたいとしましょう。
当然、これらの値はひとつのクラスとして扱いたいですね。
例えば、
というクラスを考えてみます。
このクラスを 設定ファイルに保存できるようにするには、ApplicationSettingsBase から継承し、
以下のように書き換えてやる必要があります。
随分コードが増えてしまいましたが、パターン化されていますので、 機械的にコーディングできると思います。
このクラス定義ができれば、あとは読み書きのコードを書くだけです。
読み込みは、WindowInfo のオブジェクトを生成し、プロパティにアクセスするだけです。
なお、このプログラムを最初に起動した場合は、値を読み込むことが出来ないために、
NullReferenceException 例外が発生します。この例外が出たときには、何もせずにデザイン時の値を
そのまま使います。
書き込みは、WindowsInfoの各プロパティに値を設定し、Saveメソッドを呼び出します。
なお、WindowsFormsでは、フォームデザイナーのプロパティ画面で、(ApplicationSettings) で
保存したいプロパティを設定すれば、いちいち上記のようなコードを書く必要はありません。
あくまでも、サンプルとして見てください。
実際、自動生成される Settings.Designer.cs を見てみると、ApplicationSettingsBase クラスを継承したクラスが
定義されています。
もちろん、フォームやGUIコントロールのプロパティ以外の値を設定するには、デザイナーでのサポートは
ありませんので、ApplicationSettingsBaseクラスを利用するなら、ここに書いた方法で値を設定することになります。
(続く...)
追記 (2011/07/11)
最後の文は、ちょっと語弊がある文章でした。
C#プロジェクトの Properties フォルダの、Settings.settingsを開いて表示されるデザイナー(これもデザイナー
の一種ですね)で独自の情報を格納することができます。
ただ、このシリーズでは、Settings.settingsを開いて表示される設定デザイナーを利用する方法については、割愛します。
ApplicationSettingsBase を直接使ってみることで、Settings.settingsで作成する 設定ファイルクラスを
より理解できるようになります。
2011年07月03日
C#プログラマーのための再帰処理・超入門
いげ太さんの記事に触発されて僕も書いてみた。
岩波国語辞典には、再帰→回帰 とあり、回帰の意味を見てみると、
とあります。
つまり、C#での再帰処理とは、ある処理をするのに、自分自身のメソッドを繰り返し呼び出す処理のことです。
なお、再帰は、処理だけではなく、構造においても使われます。コンピュータのフォルダ構造が
その身近な例ですね。
さて、それでは、1 から n までの整数の合計(これを sum(n)と表す)を求める処理
について考えてみます。
と表せます。
1 から (n-1) までの合計は、というと、sum(n-1) であらわすことができます。
つまり、
と定義できるわけです。
これが、分かれば、再帰コードを書くことが出来ます。
次のようなコードを書いてみました。
何をやっているかと言えば、
Sum(n) を求めるには、Sum(n-1) で自分自身のメソッドを呼び出し、1から n-1 の
合計を求め、その結果に n を加えた値を結果として、返しています。
しかし、これには、大きな欠陥があります。
実際に、動かしてもらえば、分かると思いますが、スタックオーバーフローの例外が発生してしまいます。
なぜならば、Sumメソッドが呼ばれたら、その中で、Sumメソッドを呼び出し、さらに、
その中で、Sumメソッドを呼び出し.... を繰り返すわけですから、無限に、Sum を呼び
続けてしまうわけです。
さて、ここで、While 文を使った、同様のコードを見てみましょう。
このコードでは、無限ループにならないように、i < n でループの終了判定を行っていますね。
再帰のコードも同様に、再帰の終了判定を行わないと、無限にメソッドを呼び続ける
ことになるのです。
ためしに、
とし、実行してみましょう。Sum メソッドに渡ってきた 引数 n をConsole.WriteLineで
表示するコードと、Sleepメソッドを追加しています。
※ 途中で、Ctrl+Cを押して、プログラムを終了させてください。
と表示され、Sumの引数に 0 以下の値が渡ってきていることが確認できます。
これを見れば、1 がきたところで、再帰呼び出しをストップすれば良いことがわかります。
それでは、再帰版のSumメソッドに終了判定を入れたいと思います。
※ 一時変数の resultは取り除いています。
問題は、コメントにも書いたように、n が 1の時に何を書くかです。
具体的に、Sum(1) の結果が何かを考えてみると、1 が返ればよいわけですから、
最終的なコードは、次のようになります。
と定義できると書きましたが、これはより正確には、
となります。
この定義をそのまま、C#のコードに書き下したものが、上記Sumメソッドとなります。
これは、メソッドの定義が、手続き的な「処理の記述」から、問題の構造そのものを表す
「問題の定義」に近くなっていることを示しています。(言い換えると、HowからWhatですね)
コード自体も、とてもすっきりしていますね。whileをつかったコードのごちゃごちゃ感が
こちらにはありません。
ただ、手続きを書くことに慣れているプログラマーには、これでは、どう動くのかが
良くわからないという方も多いと思います。実際に、僕が若いころに再帰を学んだ時はそうでした。
ということで、どう動いているのかを確認してみましょう。
以下のようにデバッグ行を追加してみます。
この結果は、
これを言葉で言い換えると、次のようになるかと思います。
1. Sum(5)を求めるには、そのひとつ前のSum(4)を知らなければならない、だからSum(4)を呼ぶ。
2. Sum(4)を求めるには、そのひとつ前のSum(3)を知らなければならない、だからSum(3)を呼ぶ。
3. Sum(3)を求めるには、そのひとつ前のSum(2)を知らなければならない、だからSum(2)を呼ぶ。
4. Sum(2)を求めるには、そのひとつ前のSum(1)を知らなければならない、だからSum(1)を呼ぶ。
5. Sum(1) は、1だから、1 を返す。
6. Sum(1)が求まったから、Sum(2) は、Sum(1) + 2 で 1 + 2 になるので、3を返す。
7. Sum(2)が求まったから、Sum(3) は、Sum(2) + 3 で 3 + 3 になるので、6を返す。
8. Sum(3)が求まったから、Sum(4) は、Sum(3) + 4 で 6 + 4 になるので、10を返す。
9. Sum(4)が求まったから、Sum(5) は、Sum(4) + 5 で 10 + 5 になるので、15を返す。
これからわかるように、C#における再帰呼び出しは、メソッドをどんどん深く呼び出し続けるため、
スタックを消費することになります。
大抵の場合は、これでも問題はありませんが、解くべき問題によっては、スタックオーバーが 起こりえます。この点は注意が必要です。
しかし、その欠点を補ってあまりあるパワーが再帰にはあります。
それは、再帰的な構造のデータを処理する際に、発揮されます。
先ほどあげた、フォルダ構造を扱ったり、家系図のような階層構造(Tree構造)のデータを扱う際には、 再帰はとても有効な手段となります。
ボードゲームのような先読みを処理を行うにも、再帰は有効(というか必須)です。
また、リンクリストを扱ったり、今回のような通常の繰り返し処理や、リトライ処理などでも 再帰が使えますね。
なお、いげ太さんの記事では、末尾再帰によるコードが示されていますが、
C#のコンパイラには、末尾再帰の最適化が組み込まれていません。 そのために、ここでは、末尾再帰のコードは示していません。
末尾再帰について知りたければ、こことかここを見てください。
ちなみに、僕のWebサイト「Gushwell"s C# Programming Page」の「C# プログラム小品集」
に掲載したプログラムでも、再帰を使っているプログラムがたくさんあります。
例えば、
階乗の計算
http://gushwell.ifdef.jp/etude/Factorial.html
すべての順列を求める
http://gushwell.ifdef.jp/etude/Permutation.html
ヒルベルト曲線
http://gushwell.ifdef.jp/etude/HirbertCurve.html
8-Queenパズル
http://gushwell.ifdef.jp/etude/nQueen.html
最大面積の領域を求める
http://gushwell.ifdef.jp/etude/MaxArea.html
などです。興味がありましたら、読んでみてください。
岩波国語辞典には、再帰→回帰 とあり、回帰の意味を見てみると、
(2) 〔名〕処理手続きや規則の定義に、それ自身を繰り返し使うような仕方。
とあります。
つまり、C#での再帰処理とは、ある処理をするのに、自分自身のメソッドを繰り返し呼び出す処理のことです。
なお、再帰は、処理だけではなく、構造においても使われます。コンピュータのフォルダ構造が
その身近な例ですね。
さて、それでは、1 から n までの整数の合計(これを sum(n)と表す)を求める処理
について考えてみます。
sum(n) = 1 + 2 + 3 + 4 + ... + (n-2) + (n-1) + n
と表せます。
1 から (n-1) までの合計は、というと、sum(n-1) であらわすことができます。
つまり、
sum(n) = sum(n-1) + n
と定義できるわけです。
これが、分かれば、再帰コードを書くことが出来ます。
次のようなコードを書いてみました。
int Sum(int n) {
int result = Sum(n-1) + n;
return result;
}
何をやっているかと言えば、
Sum(n) を求めるには、Sum(n-1) で自分自身のメソッドを呼び出し、1から n-1 の
合計を求め、その結果に n を加えた値を結果として、返しています。
しかし、これには、大きな欠陥があります。
実際に、動かしてもらえば、分かると思いますが、スタックオーバーフローの例外が発生してしまいます。
なぜならば、Sumメソッドが呼ばれたら、その中で、Sumメソッドを呼び出し、さらに、
その中で、Sumメソッドを呼び出し.... を繰り返すわけですから、無限に、Sum を呼び
続けてしまうわけです。
さて、ここで、While 文を使った、同様のコードを見てみましょう。
static int WhileSum(int n) {
int result = 0;
int i = 0;
while (i < n) {
result = result + i;
i++;
}
return result;
}
このコードでは、無限ループにならないように、i < n でループの終了判定を行っていますね。
再帰のコードも同様に、再帰の終了判定を行わないと、無限にメソッドを呼び続ける
ことになるのです。
ためしに、
class Program {
static void Main(string[] args) {
Console.WriteLine(Sum(5));
}
static int Sum(int n) {
Console.Write("{0} ", n);
System.Threading.Thread.Sleep(100);
int result = Sum(n - 1) + n;
return result;
}
}
とし、実行してみましょう。Sum メソッドに渡ってきた 引数 n をConsole.WriteLineで
表示するコードと、Sleepメソッドを追加しています。
※ 途中で、Ctrl+Cを押して、プログラムを終了させてください。
5 4 3 2 1 0 - 1 - 2 -3 ...
と表示され、Sumの引数に 0 以下の値が渡ってきていることが確認できます。
これを見れば、1 がきたところで、再帰呼び出しをストップすれば良いことがわかります。
それでは、再帰版のSumメソッドに終了判定を入れたいと思います。
static int Sum(int n) {
if (n == 1)
; // ここに何を書く?
else
return Sum(n - 1) + n;
}
※ 一時変数の resultは取り除いています。
問題は、コメントにも書いたように、n が 1の時に何を書くかです。
具体的に、Sum(1) の結果が何かを考えてみると、1 が返ればよいわけですから、
最終的なコードは、次のようになります。
static int Sum(int n) {
if (n == 1)
return 1;
else
return Sum(n - 1) + n;
}
なお、最初に、Sum(n)は、sum(n) = sum(n-1) + n
と定義できると書きましたが、これはより正確には、
n == 1 の時
Sum(n) = 1
n > 1 の時
Sum(n) = Sum(n-1) + n
となります。
この定義をそのまま、C#のコードに書き下したものが、上記Sumメソッドとなります。
これは、メソッドの定義が、手続き的な「処理の記述」から、問題の構造そのものを表す
「問題の定義」に近くなっていることを示しています。(言い換えると、HowからWhatですね)
コード自体も、とてもすっきりしていますね。whileをつかったコードのごちゃごちゃ感が
こちらにはありません。
ただ、手続きを書くことに慣れているプログラマーには、これでは、どう動くのかが
良くわからないという方も多いと思います。実際に、僕が若いころに再帰を学んだ時はそうでした。
ということで、どう動いているのかを確認してみましょう。
以下のようにデバッグ行を追加してみます。
static void Main(string[] args) {
Console.WriteLine(Sum(5));
Console.ReadLine();
}
static int Sum(int n) {
Console.WriteLine("Sum({0}) called", n);
if (n == 1) {
return 1;
} else {
int a = Sum(n - 1);
Console.WriteLine("Sum({0}) -> {1}", n - 1, a);
return a + n;
}
}
この結果は、
Sum(5) called Sum(4) called Sum(3) called Sum(2) called Sum(1) called Sum(1) return 1 Sum(2) return 3 Sum(3) return 6 Sum(4) return 10 Sum(5) return 15 15となります。
これを言葉で言い換えると、次のようになるかと思います。
1. Sum(5)を求めるには、そのひとつ前のSum(4)を知らなければならない、だからSum(4)を呼ぶ。
2. Sum(4)を求めるには、そのひとつ前のSum(3)を知らなければならない、だからSum(3)を呼ぶ。
3. Sum(3)を求めるには、そのひとつ前のSum(2)を知らなければならない、だからSum(2)を呼ぶ。
4. Sum(2)を求めるには、そのひとつ前のSum(1)を知らなければならない、だからSum(1)を呼ぶ。
5. Sum(1) は、1だから、1 を返す。
6. Sum(1)が求まったから、Sum(2) は、Sum(1) + 2 で 1 + 2 になるので、3を返す。
7. Sum(2)が求まったから、Sum(3) は、Sum(2) + 3 で 3 + 3 になるので、6を返す。
8. Sum(3)が求まったから、Sum(4) は、Sum(3) + 4 で 6 + 4 になるので、10を返す。
9. Sum(4)が求まったから、Sum(5) は、Sum(4) + 5 で 10 + 5 になるので、15を返す。
これからわかるように、C#における再帰呼び出しは、メソッドをどんどん深く呼び出し続けるため、
スタックを消費することになります。
大抵の場合は、これでも問題はありませんが、解くべき問題によっては、スタックオーバーが 起こりえます。この点は注意が必要です。
しかし、その欠点を補ってあまりあるパワーが再帰にはあります。
それは、再帰的な構造のデータを処理する際に、発揮されます。
先ほどあげた、フォルダ構造を扱ったり、家系図のような階層構造(Tree構造)のデータを扱う際には、 再帰はとても有効な手段となります。
ボードゲームのような先読みを処理を行うにも、再帰は有効(というか必須)です。
また、リンクリストを扱ったり、今回のような通常の繰り返し処理や、リトライ処理などでも 再帰が使えますね。
なお、いげ太さんの記事では、末尾再帰によるコードが示されていますが、
C#のコンパイラには、末尾再帰の最適化が組み込まれていません。 そのために、ここでは、末尾再帰のコードは示していません。
末尾再帰について知りたければ、こことかここを見てください。
ちなみに、僕のWebサイト「Gushwell"s C# Programming Page」の「C# プログラム小品集」
に掲載したプログラムでも、再帰を使っているプログラムがたくさんあります。
例えば、
階乗の計算
http://gushwell.ifdef.jp/etude/Factorial.html
すべての順列を求める
http://gushwell.ifdef.jp/etude/Permutation.html
ヒルベルト曲線
http://gushwell.ifdef.jp/etude/HirbertCurve.html
8-Queenパズル
http://gushwell.ifdef.jp/etude/nQueen.html
最大面積の領域を求める
http://gushwell.ifdef.jp/etude/MaxArea.html
などです。興味がありましたら、読んでみてください。
Posted by gushwell at
23:00
│Comments(2)