再帰プログラムの非再帰形プログラムへの変換
この前の院試でも出題されたのだけど、任意の再帰プログラムは仮想スタックを用いることで非再帰形へと変換することが出来る。
恥ずかしながら院試の本番ではウロ覚えで上手く解答出来なかったが、この程度のことは学部初等レベルの知識なのでちゃんと復習することにした。
実際には二分木で与えられたのだけれど、ここでは簡単のため配列表現を用いた。
元のプログラム
1 #include <stdio.h>
2 #include <stdlib.h>
3
4 #define MAX 11
5
6 int t[] = {0,1,2,3,4,5,6,7,8,9,10};
7
8 int left(int n) { return n*2+1; }
9 int right(int n) { return n*2+2; }
10
11 void traverse(int t[],int n)
12 {
13 if(n < MAX) {
14 traverse(t,left(n));
15 printf("%d\n",t[n]);
16 traverse(t,right(n));
17 }
18 }
19
20 main()
21 {
22 traverse(t,0);
23 exit(0);
24 }ここで、traverseを非再帰形へと変換するのが最終目標となる。
ステップ1 ラベルの導入と末尾再帰の消去
末尾再帰はそのままループの形式に変換することが出来る。ただしこの段階では後々のためにラベルを作ってgotoを用いた方がいい。
void traverse(int t[],int n)
{
L0:
if(n < MAX) {
traverse(t,left(n));
printf("%d\n",t[n]);
n = right(n);
goto L0;
}
}
ステップ2 仮想スタックの導入による再帰の消去
末尾再帰でない再帰形は、仮想スタックを用いて引数などの要素を退避させる必要がある。これはマシン語のサブルーチン呼び出しの手法をシミュレートするような形になる。
今回の場合は木の枝部分を保持するスタックを導入する。
// これ以外は上と同じ
int stack_tbl[1000];
int stackp = 0;
int stackempty() { return (stackp == 0); }
void
push(long n) {
stack_tbl[stackp++] = n;
}
int
pop() {
if (!stackempty()) return stack_tbl[--stackp];
else {
printf("stack empty\n");
return 0;
}
}
void traverse(int t[],int n)
{
L0:
if(n < MAX) {
push(n);
n = left(n);
goto L0;
}
if(!stackempty()) {
n = pop();
printf("%d\n",t[n]);
n = right(n);
goto L0;
}
}サブルーチン呼び出しに近いことをやっていることに注目する。ステップ1でgotoを用いたのはこのためである。
ここまでで実際的には問題ないのだけど、gotoを用いるのはあまり綺麗とは言えない。以下のように段階的にループに変換する。
ステップ3 無限ループ+continue形への変換
void traverse(int t[],int n)
{
for(;;) {
if(n < MAX) {
push(n);
n = left(n);
continue;
}
if(stackempty()) {
return;
}
n = pop();
printf("%d\n",t[n]);
n = right(n);
}
}これで良いとも思えるが、continueはgotoと大して変わらんという意見もある。この例ではこれも消去することが出来る。
ステップ4 continueの消去
void traverse(int t[],int n)
{
for(;;) {
while(n < MAX) {
push(n);
n = left(n);
}
if(stackempty()) {
return;
}
n = pop();
printf("%d\n",t[n]);
n = right(n);
}
}これが非再帰版traverseの最終形となる。
他の場合と課題
他に引数を与えるような場合はそれもスタックに保存すれば良い。これもサブルーチン呼び出しと同じようにpopを複数回呼び出して値を戻すような感じになる。
しかし、内部で数回末尾再帰でない再帰関数を呼ぶような関数の変換方法が分からない。学校のテキストを見てもそのような関数の変換例は書いてなかった。もっと調べる必要がありそうだ。実際には複雑な再帰形では変換が困難になるのかもしれない。
参考文献
- 学校のプログラミング通論のテキスト
