独自に作成したスタックを使用して非末尾再帰関数を反復関数に変換する場合、再帰呼び出しの後に来るコードの部分、別名末尾を処理する一般的な方法は何ですか?
次の関数は、迷路内のすべての可能なパスを探索し、スタック内の他のパスにアクセスするために、以前にアクセスしたパスに再アクセスすることになっています。
struct node{
int id;
bool free;
int neighborNode[4];
int toProcess;
} nodeMap[100];
void findPath(int current){
visited[current] = true;
int i;
for (i=0; i < 4; i++){
if(nodeMap[nodeMap[current].neighborNode[i]].free == true && visited[nodeMap[current].neighborNode[i]] == false && nodeMap[current].neighborNode[i] != -1){
path[cc] = nodeMap[nodeMap[current].neighborNode[i]].id;
cc++;
findPath(nodeMap[current].neighborNode[i]);
path[cc] = nodeMap[current].id;
cc++;
}
}
}
コードの再帰部分は反復に簡単に変換できます (toProcess
スタックに保存されず、すべての子を処理するために必要なループのインデックスを模倣するためにフィールドを使用しました)。
void findPath(){
if (isEmpty())
return;
else {
node temp = pop();
visited[temp.id] = true;
if (temp.toProcess < 3) {
temp.toProcess++;
push(temp);
temp.toProcess--;
}
if(nodeMap[temp.neighborNode[temp.toProcess]].free == true && visited[temp.neighborNode[temp.toProcess]] == false && temp.neighborNode[temp.toProcess] != -1){
path[cc] = nodeMap[temp.neighborNode[temp.toProcess]].id;
cc++;
push(nodeMap[temp.neighborNode[temp.toProcess]]);
}
}
}
しかし、アルゴリズムが逆方向に移動して以前に見たノードを再訪し、他の可能なパス (テール) を探索する部分、つまりpath[cc] = nodeMap[current].id;
&cc++;
はメソッドの反復バージョンには適合しないようです! これに対する一般的なアプローチはありますか?それともケースごとに違う?とにかく、この場合にテール部分を実装する方法について何か提案はありますか?