再帰関数がスタックオーバーフローを引き起こしています

Question

迷路内のパスを見つけるために作成した関数に問題があります。そのパス上にある場合はtrueを返し、終了する場合はfalseを返します。迷路は解決できません。変数の " - 1s"をチェックしようとするとスタックオーバーフローエラーが発生しますが、ベースケースはそれを防止する必要があります。再帰でスタックスペースを少なくする方法はありますか？ここでは、必要なスタック領域の量が無限大であるとき、無限未満のものはまだ無限であるという単純な理由のために、「より少ないスタック領域」を使用することはできません私のコード

bool Pathfinder::check(string& maze, stack<string>& path, int x, int y, int z) 
{int checking = 0; 
    if ((x == 4) && (y == 4) && (z == 4)) 
    { 
     path.push(this->createCoords(x, y, z)); 
     return true; 
    } 
    else 
    { 
     if ((x + 1) < 1 || (x + 1) > columns) 
     { 
      return false; 
     } 
     if ((y + 1) < 1 || (y + 1) > rows) 
     { 
      return false; 
     } 
     if ((z + 1) < 1 || (z + 1) > floors) 
     { 
      return false; 
     } 
     if ((x < 0) || (y < 0) || (z < 0)) 
     { 
      return false; 
     } 
     if (this->getValue(maze, x, y, z) == 1) 
     { 
      this->setValue(maze, x, y, z, 2); 
     } 
     else 
     { 
      return false; 
     } 
    } 


    if (this->check(maze, path, x + 1, y, z) || 
     this->check(maze, path, x, y + 1, z) || 
     this->check(maze, path, x, y, z + 1)) 
    { 
     checking++; 
    } 
    if (this->check(maze, path, x - 1, y, z) && checking == 1) //Overflow error comes from here 
    { 
     checking++; 
    } 
    if (this->check(maze, path, x, y - 1, z) && checking == 2) 
    { 
     checking++; 
    } 
    if (this->check(maze, path, x, y, z - 1) && checking == 3) 
    { 
     path.push(this->createCoords(x, y, z)); 

     return true; 
    } 

    return false; 
} 

Answer 1

です。それが無限の意味です。示されたアルゴリズムは論理的に欠陥があり、明らかに無限再帰をもたらす。次のようにのは、これらの再帰呼び出しの一部にラベルを付けてみましょう：

if (this->check(maze, path, x + 1, y, z) || // A 
    this->check(maze, path, x, y + 1, z) || // B 
    this->check(maze, path, x, y, z + 1))  // C 
{ 
    checking++; 
} 

if (this->check(maze, path, x - 1, y, z) && checking == 1) // D 
{ 
    checking++; 
} 

checkingの初期値は、我々は上記のコードに基づいて、以下の結論を引き出すことができます0です。

1）再帰呼び出しAが常に発生します。

が

2）A、またはB、またはC再帰的なCALのリターンのいずれかtrue

3の座標のいくつかのセットがあります）と条件2）が成立したときに、再帰呼び出しDは常に行われます。

したがって、条件 "2）"が成立すると、無限再帰が保証されます。再帰呼び出しAは、再帰呼び出しDを論理的に無限再帰にします。

これは、条件式2)が成立する再帰呼び出しの前に、再帰呼び出しAがx+1を渡すためです。そして、再帰呼び出しの条件内で「2）」、再帰呼び出しでD.

、その結果、真と評価さしかし、これは最初に同じyで、二番目に、その後x+1、x+1-1を渡して、二つの連続するネストされた再帰呼び出しになり値はzです。 2回目の再帰呼び出しでは、祖父母呼び出しとしてx,y、およびzの同じ値が渡されます。この無限再帰を停止するものは何もありません。

示されたアルゴリズムは根本的に壊れています。なぜそれが壊れているのか、正しいアルゴリズムは何かを理解する必要があります。これは質問の限られた情報に基づいて答えられることはできません。なぜなら、些細なことで決定できる唯一の事柄は理由と、無限の再帰が起こる理由の説明です。むしろ明らかです。