再帰処理をループ処理に変換

Question

趣味プログラマです。このカテゴリ一個前の質問 https://oshiete.goo.ne.jp/qa/10782948.html のご回答の中で > 関数の再帰呼び出しは必ずループで置き換えられるというものがありました。このこと自体は、以前にも目にしたことがあるのですが、変換例はいずれも単純な再帰関数のものでした。そこで質問なのですが2分木を辿るような再帰プログラムの場合は、どの様なループ処理に変換されるのか、教えてください。具体的なソースをご提示いただければ嬉しいです（C言語でなくても有名どころの言語ならOKです）また、その処理はメモリ使用の観点において、再帰よりも効率が良くなりますか？個人的には、プログラム中にスタックの様なものを用意しなければならないので、あまり効率よくならない様な気がします。ご回答よろしくお願い致します。 ※以下は2分木の合計を再帰で求める例です。 ---- #include #include typedef struct Node_t Node; struct Node_t { int value; Node* left; Node* right; }; Node* NewNode(int val){ Node* p = malloc(sizeof(Node)); p->value = val; p->left = NULL; p->right = NULL; return p; } int Sum(Node* p){ int lsum = 0; int rsum = 0; if(p->left != NULL) lsum = Sum(p->left); if(p->right != NULL) rsum = Sum(p->right); return lsum + rsum + p->value; } int main() { int sum = 0; Node* header; header = NewNode(10); header->left = NewNode(20); header->right = NewNode(30); header->left->left = NewNode(40); header->right->right = NewNode(50); /*もっと深く2分木を作成 */ sum = Sum(header); printf("%d ", sum); return EXIT_SUCCESS; } ----

k-841 · Accepted Answer

N分木の総舐めだとすると、こんな感じじゃないですか？
最初に言っておきますが、メモリ効率は平均的によろしくないです。
劣悪な（深い）木よりはましというレベルです。
平衡二分木のように随時木をメンテナンスしていれば別の方法の方が効率は良いと思います。
ただ、スタック領域のメモリ不足は少なくとも私の手元の環境ではエラー検出できませんが、
ヒープ領域のメモリ不足はエラー処理はできます。
DoS攻撃などで勝手に落ちられると困るので、
少なくとも蓄積データのフルダンプや全解放ごときで落ちる心配は取り去りたいという、
ささやかな、見る人によってはくだらないこだわりのような、しかし切実な問題です。

#define N 2
struct tree
{
  struct tree *tr_parent;  // 追加要素
  struct tree *tr_next[N]; // データ構造の小修整
  int tr_val;
  int tr_ref;  // 追加要素
};

int
sum_tree(struct tree *top)
{
  struct tree *n, *prev;
  int sum = 0;
  int updown = 2;

for (n = top, n->tr_ref = 0, n->tr_parent = NULL, prev = n;
       n != NULL;) {
    if (updown == 0) {
      // case down
      n->tr_ref = 0;
      n->tr_parent = prev;
    }
    if (n->tr_ref == N) {
      sum += n->tr_val;
      n = n->tr_parent;
      updown = 1;
    } else if (n->tr_next[n->tr_ref] == NULL) {
      updown = 2;
      n->tr_ref ++;
    } else {
      updown = 0;
      prev = n;
      n = n->tr_next[n->tr_ref];
      prev->tr_ref ++;
    }
  }
  return sum;
}

実際、再帰を使わないようにする変換方法の定式なんてないと思います。
しかし、再起でなければできない処理もなく、等価な別の処理方法はあると思います。

usa3usa · Answer

Ｎｏ２です
//[オリジナルの再帰プログラムの１回の処理」で必要なX[i]が既知であれば処理をしてX[i+1]にデータを書き込み、既知の記をつける.
は、こちらのほうがわかりやすいと思うので書き換えてみました

void Sum1(Node* p){
　　if(p->flag !=0 ) return; // 計算不要
　　int lsum = 0;
　　int rsum = 0;

if(p->left != NULL && p->left->flag == 0) return; // 計算できない
　　lsum = p->left->sum;
　　if(p->right != NULL && p->right->flag == 0) return; // 計算できない
　　rsum = p->right->sum;

p->sum = lsum + rsum + p->value;
　　p->flag = 1;	// データsum は有効である印
}

usa3usa · Answer

Ｎｏ２です＞ご回答ありがとうございます。＞ただ、申し訳ありません。ご説明の方法を質問で挙げた二分木に応用するために、どのように具体化すべきか思い浮かびません。＞よろしければ、具体手なコードをご提示いただけないでしょうか？動作確認してませんが、こんな感じでできると思います。あくまで「こんな感じ」ということです。 #include #include typedef struct Node_t Node; struct Node_t { 　　int value; 　　int flag; // 追加要素　　int sum; // 追加要素　　Node* left; 　　Node* right; }; Node* NewNode(int val){ 　　Node* p = malloc(sizeof(Node)); 　　p->value = val; //・途中結果に「未知」の記をつける　　p->flag = 0;　　　p->sum = 0; 　　p->left = NULL; 　　p->right = NULL; 　　return p; } /* 使用しないのでコメントアウト int Sum(Node* p){ 　　int lsum = 0; 　　int rsum = 0; 　　if(p->left != NULL) lsum = Sum(p->left); 　　if(p->right != NULL) rsum = Sum(p->right); 　　return lsum + rsum + p->value; } */ //[オリジナルの再帰プログラムの１回の処理」で必要なX[i]が既知であれば処理をしてX[i+1]にデータを書き込み、既知の記をつける. void Sum1(Node* p){ 　　if(p->left == NULL && p->right == NULL) { 　　　　p->sum = p->value; 　　　　p->flag = 1; 　　} else if(p->left == NULL && p->right != NULL && p->right->flag !=0) { 　　　　p->sum = p->value + p->right->sum; 　　　　p->flag = 1; 　　} else if(p->left != NULL && p->right == NULL && p->left->flag != 0) { 　　　　p->sum = p->value + p->left->sum; 　　　　p->flag = 1; 　　} else if(p->left != NULL && p->left->flag != 0 && 　　　　　　　p->right != NULL && p->right->flag != 0){ 　　　　p->sum = p->value + p->left->sum + p->right->sum; 　　　　p->flag = 1; 　　} } #define SIZE 10 int main() { 　　int sum = 0; 　　Node* header; // 途中結果を保存する変数X[i] を用意する　　Node* headerList[SIZE];　　　int headerListSize = 0; 　　header = headerlist[headerListSize++] = NewNode(10); 　　header->left = headerlist[headerListSize++]= NewNode(20); 　　header->right = headerlist[headerListSize++]= NewNode(30); 　　header->left->left = headerlist[headerListSize++]= NewNode(40); 　　header->right->right = headerlist[headerListSize++]= NewNode(50); 　 /*もっと深く2分木を作成 */ //　X[N]に既知の記をつけたなら処理終了　　while(header.flag == 0) { 　　　　for(i=0; i

Tacosan · Answer

構文解析には各種の構文クラスに対応していろいろな手法があるんだけど, どういうものを想定してますか? 例えば LL(1) の再帰下降パーザだったら, スタックを使えば再帰しなくていいってのは有名ですよね.

余談だけど
int Sum(Node* p){
　int lsum = 0;
　int rsum = 0;

if(p->left != NULL) lsum = Sum(p->left);
　if(p->right != NULL) rsum = Sum(p->right);
　return lsum + rsum + p->value;
}
って「末尾再帰」じゃないよねぇ＞#5.

cametan_42 · Answer

これ単に命題が間違ってるだけ、だと思うんですが。

> 関数の再帰呼び出しは必ずループで置き換えられる

そうなんですか?
聞いたことないです。
多分これと間違ってるんじゃ・・・・・。

> 末尾再帰の関数は(例えばアセンブリレベルで)ジャンプ構文に置き換えられる

そもそもC/C++やってる人って「再帰」は知ってても「末尾再帰って何?」って人が結構多いようなんで・・・。

✗ 末尾再帰じゃない例:

int func(int n) {
　....
　return a + func(n-1); //これは元のfuncを呼び出した「他」に別の操作をしてるので末尾再帰じゃない
}

○ 末尾再帰な例

int func(int n) {
　....
　return func(n-1); // どんな引数を与えても元のfuncを「呼び出す」以外に何もしてない
}

具体例で言うと次のような感じですか。

✗ 末尾再帰じゃない例:
int rec(int n){
　if (n == 1)
　　return 5;
　else
　　return 3 * rec(n-1) + 4; // recを呼び出す以外に色々やってる
}

○ 末尾再帰の例:
int rec(int n, int acc){
　if (n == 1)
　　return acc;
　else
　　return rec(n-1, 3*acc+4); // 引数内はいじってもrec以外は呼び出してない
}

後者の形式の場合、

・コンパイラによってはアセンブリレベルでループ構文と同等のコードを吐いてくれる(末尾再帰最適化)
・「手作業で」ループ構文に書き換えるのも可

って話なだけだと思うんですが、当然前者だとそれは出来ません。
故に、実は

https://oshiete.goo.ne.jp/qa/10782948.html

の問題の場合、例示されてるforループでの解に理論的に同等なのは、ここで提示されている「末尾再帰」のコードであって、実は(元のページの)再帰のコードではないのです。この二つは「全く違います」。

注: だから余計な事やって「再帰の内部状態を想像して・・・」なんつーのは無駄だ、って言ったのです。
本質的に「意味が違う」二つのコードを並べて「結果が同じだから同じ計算方法だよね?」って言うのがどれだけ無駄な事なのか・・・(計算方法が違っても同じ解に到達する事は良くあることですが(目的が同じな為)、一方、「同じ答えを得た」からと言って「同一種の計算方法である」と言う結論をすぐに引き出せるわけがありません)。
「再帰の内部状態を想像してトレースする」なんつー屁理屈やっても、結果本質的に同等なコードを取り違えるようだったら全く意味が無い「くだらない教育方針だ」と言う事なんですよ。おわかりですか?

さて、と言う事だと、例示コードの再帰部分

int Sum(Node* p){
　int lsum = 0;
　int rsum = 0;

if(p->left != NULL) lsum = Sum(p->left);
　if(p->right != NULL) rsum = Sum(p->right);
　return lsum + rsum + p->value;
}

あるいは次のような短くした形、

int Sum(Node* p) { 
　int lsum = p->left == NULL? 0: Sum(p->left);
　int rsum = p->right == NULL? 0: Sum(p->right);
　return lsum + rsum + p->value;
}

は変数に代入して「形式的」には末尾再帰を装っていますが、実質的には次のコードと全く同じです。

int Sum(Node* p) {
　if (p == NULL){
　　return 0;
　} else {
　　return p->value + Sum(p->left) + Sum(p->right); // 変数lsumとrsumを消せばこれと内容は同じ
　}
}

これは末尾再帰じゃありませんね。
従ってループ構文に「簡単には」変換出来ません。
故に、結局ある程度スタックを消費する「非効率な」再帰のまま、でいるしかないでしょうね。

注: C++辺りなら、取り敢えずCPS(継続受け渡し方式)で「形式的」には末尾再帰に出来る筈。だけどジャンプ構文に変換して「効率的な」ループに書き換えられるのか、と言うとそれは別問題で、「形式的な」末尾再帰には注意が必要。

tknakamuri · Answer

>質問で挙げた足し算の様なものであれば、ノードを処理する順番は関係ありませんが。
>構文解析のようなものについてはFIFOでは対応できないと思います。

質問の趣旨ってそこなんですか?

考えられるありとあらゆる再帰の解法を網羅しろという話なら
私には無理。こべつの解法を知っているだけです。

それと構文解析の再帰は複雑さの割に深さが浅いので
わざわざループに直したりしないと思います。

tknakamuri · Answer

必ず置き換えられるかは証明をみたことがないので分かりませんが
このてのものは簡単。もう充分お分かりと思いますがキューを使います。

・処理キューを作り、根っこ(root)のノードを登録する
・処理キュ―が空なら終了。そうでなければ以下を繰り返す(ループ)
  ■処理キューからノードを取りだし処理する
  ■次に処理すべきノードを処理キューに登録する

充分高速に動くと思いますし、スタックオーバフローの恐れがあるなら
やるしか有りません。

usa3usa · Answer

>そこで質問なのですが2分木を辿るような再帰プログラムの場合は、どの様なループ処理に変換されるのか、教えてください。

2分木を辿るような再帰プログラムに限らず、再帰プログラムなら以下の方法でループ処理に変換できます。

・途中結果を保存する変数X[i] を用意する
・途中結果に「未知」の記をつける
・初期状態に当たるX[0]に値を代入して「既知」の記をつける
while(1){
　for(i=1; i<N; i++) {
・「オリジナルの再帰プログラムの１回の処理」で必要なX[i]が既知であれば処理をしてX[i+1]にデータを書き込み、既知の記をつける.
・X[N]に既知の記をつけたなら処理終了
　}
}

＞また、その処理はメモリ使用の観点において、再帰よりも効率が良くなりますか？
プログラミング次第、問題次第で一般論は語れません

rinkun · Answer

こういうのは『再帰処理 ループ変換』とかで検索すると結構答えがある。
一例: 各種典型再帰関数を非再帰に変換する http://d.hatena.ne.jp/sune2/20130129/1359429399

まあ末尾再帰以外では基本スタックを再現することになりますね。ただスタックを自前で実装しても関数呼び出しがなくなるだけでかなり実行効率は上がるはずですよ。関数呼び出しだとスタックフレームの構築がけっこうなオーバーヘッドになるけど、自作スタックならそういうものは必要ないですし必要最小限の情報だけで済みますから。
その代わり書く手間は増えますけど。

再帰処理をループ処理に変換

N分木の総舐めだとすると、こんな感じじゃないですか？

Ｎｏ２です

Ｎｏ２です

構文解析には各種の構文クラスに対応していろいろな手法があるんだけど, どういうものを想定してますか? 例えば LL(1) の再帰下降パーザだったら, スタックを使えば再帰しなくていいってのは有名ですよね.

これ単に命題が間違ってるだけ、だと思うんですが。

>質問で挙げた足し算の様なものであれば、ノードを処理する順番は関係ありませんが。

必ず置き換えられるかは証明をみたことがないので分かりませんが

>そこで質問なのですが2分木を辿るような再帰プログラムの場合は、どの様なループ処理に変換されるのか、教えてください。

こういうのは『再帰処理 ループ変換』とかで検索すると結構答えがある。

似たような質問が見つかりました

このQ&Aを見た人はこんなQ&Aも見ています

関連するカテゴリからQ&Aを探す

このQ&Aを見た人がよく見るQ&A

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング

こういうのは『再帰処理ループ変換』とかで検索すると結構答えがある。