うらおブログ(移転しました)スマートフォン用の表示で見るやねうらおブログ(移転しました)この広告は、90日以上更新していないブログに表示しています。2005-10-08やねう企画2005年入社問題解答と解説(3)program(昨日の解説の続き)再帰を仮想スタックの導入により非再帰に変換するという話をした。実は、仮想スタックを導入すれば、“いつでも”再帰は非再帰に変換できる。賢いコンパイラならば自動的にやってしまうだろう。それを人間様が「出来ない」というのはどこかおかしな話だ。「仮想スタック」を導入と言ったが、場合によっては、導入して非再帰型プログラムに書き換えたあと、縮退して仮想スタックを用いなくても済むプログラムになることがある。recursion(末尾再帰)を仮想スタックを導入して書き換えようとしたとき、最終的には縮退して仮想スタック自体が消去出来る。同様に、有名な例としては「ハノイの塔」のプログラムを“仮想スタックを用いないで”、非再帰に変形できるという事実がある。これについては、google先生が、私の6年前に書いた(電波じみた)記事が「いいんでないの?」と教えてくれたので、手前味噌ながら紹介しておく。http://bm98.yaneu.com/rsp/rsp30to37.html第33回,第34回を参照のこと。仮想スタックを導入して、非再帰に変換する手順を一般化して考えていく。何かしらの処理をg(),h()と書く。関数の型は便宜上intと書いておき、変数宣言もしないで使う。break;g();}}と書き換えられることは自明。ループを一つ作って、再帰停止条件でのreturnをbreakと書き換えれば良い。なるのかという部分についてもっと突っ込んだ説明をしようと思うと、「continuation(継続)」という概念の説明が必要となるのだけれど、ここでは割愛する。いう概念なしでも以下の説明でわかる。末尾再帰ではないh();}この場合は、さきほどの例と同じスタイル(whileがあって、return→continueという書き換えで)で破綻なく書こうと思うと仮想スタックが必要になる。書き換えルールは、詳しく説明しないが、変換前のプログラムと変換後のプログラムとを見比べれば法則性が見えてくるだろう。この場合、pushで積んでいるのは関数の呼び出し痕跡である。実際には引数として何もとっていないので、この場合、関数の呼び出し深さを表現しているに過ぎない。このpush/popは、SL(StackLevel)という概念を導入すれば、単に次のように書き換えることは出来る。}g();++SL;}while(SL--){h();}}ところで、このような仮想スタックを導入する方法を、最初の末尾再帰の例に適用してみると、以下のようになる。continue;g();++SL;}}と書き換えることが出来て、ループのなかで--と++を連続して繰り返しているので、この部分が簡約できて、(「++SL」を行なわないのはcontinueを実行されたときに限るので、このときにループを抜けることは自明。break;g();}}となることに気づくはずだ。要するに、末尾再帰から非再帰へは、「仮想スタック導入→SLでの表現に簡約→SL表現の除去」という流れによって縮退していたのだ。この結果だけが広く知られることになり、「末尾再帰以外の再帰は非再帰にするのが困難」と信じているプログラマがあまりに多すぎるのだ。電子書籍になるに至るまでの話ブログちょっとだけ移転のお知らせ時代はまだゲームセンターあらしに追いつかないのかやねうら王、電王戦バージョン提出しました将棋の神様のレーティングはいくつなのか?月別アーカイブはてなブログをはじめよう!yaneuraoさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。