再帰処理を非再帰処理に書き換える場合

質問

• 再帰処理を非再帰処理に書き換える際の方法や注意点について説明します。
• 再帰処理を非再帰処理に書き換える場合、階層数の上限を設けることが重要です。
• 非再帰処理に書き換える際には、goto文や疑似スタックなどを使用する必要があることがあります。

回答No.1

kmee · ベストアンサー

別にgotoは使わなくてもいいんじゃないですか?
PTRをスタックするだけで。
ループの繰り返し

void Super::Release( PTR* pp ){
std::stack<PTR> sp; // スタックの準備
sp.push(*pp) ; // 次に処理したいノードをスタックに積む
// 関数での引数に相当。

while ( ! sp.empty() ){ // スタックが空→終了
// トップの内容を見る。スタックは変化しない
// 関数で引数の受け取りに相当
PTR p = sp.top() ;

if( p == NULL ) {
// 関数でのreturnに相当
sp.pop() ; // topは処理済みになるのでスタックから削除
continue ; // 次へ
}

if ( p->child ) { // 子があったら、
sp.push(p->child) ;// 子をスタックへ積んで
continue ; // 次へ:再帰呼び出しに相当
}

sp.push(p->next); // 次の候補であるp->nextをスタックに積む

*pp = p->next;
delete p;

sp.pop() ; // topは処理済みになるのでスタックから削除

}
}

お礼

どうもありがとうございます♪

なるほど、この場合だとループとcontinue文で出来そうですね。

ただ、このコードでは
実際やってみれば分かりますが

namespace Debug {
void f(int i);
void f(const void* );
}

class AAA : Super { //実験を楽にするためだけなので超適当

void Save( MemoryMap* ) const override {}
public:
AAA*& Next() const { return (AAA*&)next; }
AAA*& Child() const { return (AAA*&)child; }
int i;
AAA(int a) : i(a){}
~AAA(){ Debug::f(i); }

};

namespace Debug { //各状況チェック
void f(int i){
TCHAR c[20];
_stprintf_s(c,20,_T("%d\r\n"),i);
OutputDebugString(c);
}
void Debug::f( const Void* p ){
TCHAR c[100];
_stprintf_s(c,100,_T("%08p\r\n"),p);
OutputDebugString(c);
}
}

で、基底クラスのデストラクタは

Super::~Super(){ static int num=0; Debug::f(++num); }

にかえ

AAA* base = new AAA(423);
base->Next() = new AAA( 5464 );
base->Child() = new AAA( 5555 );
base->Next()->Child() = new AAA( 777 );
base->Next()->Next() = new AAA( 888 );
base->Next()->Child()->Next() = new AAA( 1111 );

Super::Release( &base );
Debug::f(base);

としてみると
質問文で私が作った再帰版では

5555
1
423
2
777
3
1111
4
5464
5
888
6
00000000

となり、最後にbaseも自動的にNULLに変わって
解決ですが

kmeeさんご提示のコードでは

5555
1

までで死にます。
原因は、NULLに直らないことによる2重deleteです。

私が作った再帰版ではポインタポインタを引数として渡しているので
超お手軽な表記になっていますが

そこを考慮して簡易的に書きなおしてみると

#include <stack>

void Super::Release( PTR* pp ){

std::stack<PTR*> sp;
sp.push(pp);

for ( PTR p; !sp.empty(); ){
p = *sp.top();
if ( !p ){ sp.pop(); continue; }
if ( p->child ){ sp.push( &p->child ); continue; }
*sp.top() = p->next;
delete p;
}

}

こんなかんじですかね。
これなら

5555
1
423
2
777
3
1111
4
5464
5
888
6
00000000

で、期待どおりです。
（たぶんないとは思いますが、ややこしいコードなので、気づいてないとこでバグってる箇所があるかもしれませんｗ　見つかったら教えていただけるとありがたいです。）

ただ
今まで書いたコードについて
全て当てはまりそうかどうか
パフォーマンス、メンテなど含めgoto文とcontinue
どっちが良いかなど

まだ精査したいことがいくつかあるので
しばらくお待ちください。

補足

追加報告です。

＞原因は、NULLに直らないことによる2重deleteです。

あれ、正確にはdelete済みのやつのメンバへのアクセス違反でしたかね
そこんとこ失礼しました。
（意味的に再帰になるコードは、どう組んでも分かり辛いですねｗ）

今のところ

親よりchildの方の処理を先に行う

childより親の方の処理を先に行う

の2パターンあり得るというだけで

ノード操作関連ではcontinueとループを使った方法でも問題なさそうと分かりました。

ただ、パフォーマンス的には
10回程度やって平均が

0.002866971356706sec(stack&gotoなし)
対
0.001327178776805sec(再帰)

ぐらいになってるような状況でした。

そこで、まだコードを出していないgotoだとどうなるかですが

std::stackの微妙な仕様が若干煩わしかったので
ポインタの出し入れのみと拡張を簡単に行う自作スタックを作ってやってみました。
（キャッシュの連続性を求めてポインタの配列を動的に確保するという形で、拡張が必要になったら拡張のみは行い、縮小はせず、デストラクタで一括解放）

なお、書き忘れてましたが、プリコンパイル済みヘッダで

typedef VOID Void;
typedef size_t szt;
typedef BOOL Bool;

こんなことをやってます。

///////SimpleStack.h//////

#pragma once

class SimpleStack {

typedef Void* VP;

VP* data;
szt len, cur;
const szt cycle; //再確保が必要な場合のサイクル（要素数）

Void PushVP( VP );
bool PopVP( VP* pp ){
if (!cur) return false;
*pp = data[--cur];
return true;
}

public:

SimpleStack( szt cycle_ = 4 );
~SimpleStack();

template < typename T > Void Push( T* p ){ PushVP( (VP)p ); }
template < typename T > bool Pop( T** pp ){ return PopVP( (VP*)pp ); }

};

///////SimpleStack.cpp//////

#include "StdAfx.h"
#include "SimpleStack.h"

SimpleStack::SimpleStack( szt cycle_ ) : len(0), cur(0), cycle(cycle_) {}
SimpleStack::~SimpleStack(){ if (len) free( data ); }

Void SimpleStack::PushVP( const VP p ){

if ( cur == len ){

const szt newlen = len + cycle;
VP* t = (VP*)malloc( sizeof( VP ) * newlen );

if ( len ){
memcpy( t, data, sizeof(VP)*len );
free( data );
}

data = t;
len = newlen;

}

data[cur++] = p;

}

これで、Push(ポインタ);で押し込み
Pop(&ポインタ);で拾いつつ、戻り値チェックでスタックが空かどうか分かります。

そうすると、gotoを使う場合、一例としてはこうなります。

Void Super::Release( PTR* pp ){

SimpleStack sp;
PTR p;

while ( p = *pp ){
if ( p->child ){ sp.Push(pp); pp = &p->child; continue; }
RELEASED_ALL_CHILDREN: //ここに来る時にはpの子ノードは解放済み
*pp = p->next;
delete p;
}

if ( sp.Pop(&pp) ){ p = *pp; goto RELEASED_ALL_CHILDREN; }

}

なんと、コード量で言うとそんなには変わりがないって感じでした。

でもって、この場合やっぱりジャンプ箇所一つだけなので、フラグはなくていいですね。

そして、Push,Pop及びそれに伴うチェックがchildがらみの個所のみなので
それほど可読性も低くないと思われます。

速度ですが

0.002866971356706sec(stack&gotoなし)
0.001327178776805sec(再帰)
0.001447426842494sec(stack&goto)

こんなもんでした。

これは捨てがたいですｗ

自前のスタックでも
思ったよりも簡単かもしれない、という事が分かりましたが

その他のアイデアや突っ込みどころがありましたら是非教えてください。