Hatena::ブログ(Diary)

やねうらお−ノーゲーム・ノーライフ このページをアンテナに追加 RSSフィード

GT-Rの買取ならここですわ。どこよりも高く買取ってもらえるはず。お勧め!GT-R 買取
電王戦出場記念! 書籍化されたで! 監修したで!(`ω´) 絶版なってしもた Kindle版で復活!! 記事書いたで!
解析魔法少女美咲ちゃん マジカル・オープン!

YaneuLabs / やねうら王公式 / やねうらおにメール / twitter / プロフィール

 | 

2005-10-08 やねう企画2005年入社問題解答と解説

[] やねう企画2005年入社問題解答と解説(3)  やねう企画2005年入社問題解答と解説(3)を含むブックマーク  やねう企画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表現の除去」という流れによって縮退していたのだ。


この結果だけが広く知られることになり、「末尾再帰以外の再帰は非再帰にするのが困難」と信じているプログラマがあまりに多すぎるのだ。


(つづく)

yaneuraoyaneurao 2005/10/05 06:43 解説の難易度はこんなもんで、着いてこれてますかの??(´ω`)

melt_slincmelt_slinc 2005/10/05 09:56 「末尾再帰以外の再帰は非再帰にするのが困難」ということも知らなかった自分ですら着いてこれてます(´・ェ・`)

yaneuraoyaneurao 2005/10/05 10:04 あい(´ー`)

fkmfkm 2005/10/05 10:31 着いてこれてます〜
再帰を非再帰にするとScheme好きな教授から怒られそうですが(笑)

思兼思兼 2005/10/05 11:29 な、なんかスゴイ説明になってる。。。
「末尾再帰以外だと、再帰から戻ってきた後ローカル変数使うから、必要なローカル変数をスタックに残しておく」
「末尾再帰だと、再帰から戻ってきたあとにローカル変数使わないから、ローカル変数残しとくためのスタックイラネ」
だけじゃダメですか?

yaneuraoyaneurao 2005/10/05 11:35 ↑それは、純粋な末尾再帰のときの話。今回の問2は、末尾再帰にはなっているけれど、fを4回呼び出しての末尾再帰だから、そのパターンは当てはまらない。

ehwazehwaz 2005/10/05 11:42 頭の中がすっきりしました ヽ(´ー`)ノ
自分の失敗がベースにあるので、すごく理解しやすかったです(笑)

qinfqinf 2005/10/05 12:53 3番目のコードと4番目のコードでgとhの実行順が違う気がしますが。
前者はggghhh、後者はghghghになりませんか?

kk 2005/10/05 13:04 continueは以下の処理を今回のループでは行わない、という解釈でいいんですよね?

kk 2005/10/05 13:07 ってcontinue文はもともとCにあったんだ。使わないから忘れてた^^;;
確かにh()の呼ばれる順が変わってる気が・・・。

yaneuraoyaneurao 2005/10/05 16:34 ↑*3 しもた。書き間違えちょるヤン(´ω`) > ワシ
修正っ修正っ。

kk 2005/10/05 17:27 f()の中でf()を複数回呼ぶ場合にはh()があるとうまくない感じですね。

yaneuraoyaneurao 2005/10/06 03:07 ↑いや、それは、うまく書き換える方法がある。明日説明。

思兼思兼 2005/10/09 00:29 ↑×8 ってことは、次回は機械的にスタックを使わないループ化する方法が説明されるんですね?
楽しみにしてます。

wirewire 2005/10/09 11:32 経験則でしか理解してなかったや。
今度再帰書いて”読めない”言われたら目の前で非再帰にしてみよ。

 | 

1900 | 01 |
2004 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2012 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2013 | 01 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2014 | 01 | 02 | 03 | 04 | 06 | 08 | 10 | 11 | 12 |
2015 | 01 | 02 |


Microsoft MVP
Microsoft MVP Visual C# 2006.07-2011.06