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