1. 首頁
  2. 問答
  3. 使用遞歸函數時C++堆棧溢出

使用遞歸函數時C++堆棧溢出

2014-04-01 50 views
1

我有一個具有遞歸函數的類。我測試了100個案例，代碼工作正常。但是，我運行了另一個測試，經過幾次遞歸調用後，收到了顯示堆棧溢出的第一次機會異常，我選擇忽略它，然後出現未處理的異常，顯示內存讀取違規。使用遞歸函數時C++堆棧溢出

假設我有以下代碼（不是真正的代碼，裏面有退出條件）：

class Foo { 
    void Bar() { 
     Bar(); 
    }; 
};

當我使用調試器，我發現當時Bar被調用時，this指針接收地址號錯誤，導致Foo對象的讀數錯誤，我不知道爲什麼。

有人知道嗎？

還是應該試試？

class Foo { 
    static void Bar (Foo* obj) { 
     Foo::Bar(obj); 
    }; 
};

編輯

這裏是用來模擬遊戲寶石真正的代碼。我在scanTile方法

enum MOVE {MOVE_T, MOVE_L, MOVE_R, MOVE_B}; // Move Direction 
enum SCORE {SCORE_3 = 1, SCORE_4 = 2, SCORE_5 = 4}; // Score Types 
enum ERROR {ERR_DROP = 1, ERR_COUNT, ERR_MOVE}; // User-defined Error Code 

class Jewel { 
private: 
    UINT32 m, n, score, x, y; 
    char** map; 
    bool** scanned; 
    char move; 

    void init() { 
     map = new char*[n]; 
     scanned = new bool*[n]; 
     for (UINT32 i = 0; i < n; i++) { 
      map[i] = new char[m]; 
      scanned[i] = new bool[n]; 
     }; 
    }; 

    void reinit() { 
     for (UINT32 i = 0; i < n; i++) 
      for (UINT32 j = 0; j < n; j++) 
       scanned[i][j] = false; 
    }; 

    void uninit() { 
     for (UINT32 i = 0; i < n; i++) { 
      delete[m] map[i]; 
      delete[n] scanned[i]; 
     }; 

     delete[n] map; 
     delete[n] scanned; 
    }; 

    void fileInput() { 
     std::ifstream fInput("input.txt"); 
     fInput >> n >> m; 

     init(); 

     for (UINT32 j = 0; j < m; j++) 
      for (UINT32 i = 0; i < n; i++) 
       fInput >> map[i][j]; 

     fInput.close(); 
    }; 

    void fileOutput() { 
     std::ofstream fOutput("output.txt"); 
     fOutput << score << '\n'; 

     for (UINT32 j = 0; j < n; j++) { 
      for (UINT32 i = 0; i < n; i++) 
       fOutput << map[i][n - 1 - j] << ' '; 
      fOutput << '\n'; 
     }; 

     fOutput.close(); 

     uninit(); 
    }; 

    bool inputMove() { 
     std::cin >> x >> y >> move; 
     if ((x == -1) && (y == -1) && (move == 'A')) 
      return false; 
     else 
      return true; 
    }; 

    void outputMove() { 
     std::cout << '\n' << score << '\n'; 

     for (UINT32 j = 0; j < n; j++) { 
      for (UINT32 i = 0; i < n; i++) { 
       std::cout << map[i][n - 1 - j] << ' '; 
      }; 

      std::cout << '\n'; 
     }; 
    }; 

    void swap(char &a, char &b) { 
     char temp = a; 
     a = b; 
     b = temp; 
    }; 

    bool beginMove() { 
     switch (move) { 
     case 'T': 
      if (x < n - 1) { 
       swap(map[y][x], map[y][x + 1]); 
       return true; 
      }; 
      break; 
     case 'B': 
      if (0 < x) { 
       swap(map[y][x], map[y][x - 1]); 
       return true; 
      }; 
      break; 
     case 'L': 
      if (0 < y) { 
       swap(map[y][x], map[y - 1][x]); 
       return true; 
      }; 
      break; 
     case 'R': 
      if (y < n - 1) { 
       swap(map[y][x], map[y + 1][x]); 
       return true; 
      }; 
      break; 
     }; 

     return false; 
    }; 

    void revertMove() { 
     switch (move) { 
     case 'T': 
      swap(map[y][x], map[y][x + 1]); 
      break; 
     case 'B': 
      swap(map[y][x], map[y][x - 1]); 
      break; 
     case 'L': 
      swap(map[y][x], map[y - 1][x]); 
      break; 
     case 'R': 
      swap(map[y][x], map[y + 1][x]); 
      break; 
     }; 
    }; 

    void drop() { 
     for (UINT32 i = 0; i < n; i++) { 
      UINT32 j = 0; 

      while (j < n && map[i][j]) 
       j++; 

      if (j < n) { 
       UINT32 k = j + 1; 

       while (j < n) 
        if (!map[i][j]) { 
         while ((k < m) && !map[i][k]) 
          k++; 

         if (!map[i][k]) 
          exit(ERR_DROP); 

         map[i][j] = map[i][k]; 
         map[i][k] = 0; 

         j++; 
         k++; 
        }; 
      }; 
     }; 
    }; 

    bool scanMap() { 
     reinit(); 
     UINT32 sessionScore = 0; 

     for (UINT32 j = 0; j < n; j++) 
      for (UINT32 i = 0; i < n; i++) 
       if (!scanned[i][j]) 
        sessionScore += startScan(i, j); 

     if (sessionScore) { 
      score += sessionScore; 
      return true; 
     } else 
      return false; 
    }; 

    UINT32 startScan(const UINT32 &col, const UINT32 &row) { 
     UINT32 count = 1; 
     scanned[col][row] = true; 

     if ((row < n - 1) && !scanned[col][row + 1] && (map[col][row] == map[col][row + 1])) 
      count += scanTile(col, row + 1, MOVE_T, (0 < row) && (map[col][row] == map[col][row - 1])); 

     if ((0 < row) && !scanned[col][row - 1] && (map[col][row] == map[col][row - 1])) 
      count += scanTile(col, row - 1, MOVE_B, (row < n - 1) && (map[col][row] == map[col][row + 1])); 

     if ((col < n - 1) && !scanned[col + 1][row] && (map[col][row] == map[col + 1][row])) 
      count += scanTile(col + 1, row, MOVE_R, (0 < col) && (map[col][row] == map[col - 1][row])); 

     if ((0 < col) && !scanned[col - 1][row] && (map[col][row] == map[col - 1][row])) 
      count += scanTile(col - 1, row, MOVE_L, (col < n - 1) && (map[col][row] == map[col + 1][row])); 

     if ((count < 3) && (count != 1)) 
      exit(ERR_COUNT); 

     if (count >= 3) 
      map[col][row] = 0; 

     if (count == 1) 
      return 0; 
     else if (count == 3) 
      return count*SCORE_3; 
     else if (count == 4) 
      return count*SCORE_4; 
     else if (count >= 5) 
      return count*SCORE_5; 
    }; 

    UINT32 scanTile(const UINT32 &col, const UINT32 &row, const MOVE &direction, const bool &opposite = false) { 
     UINT32 count = 1; 
     UINT32 temp = 0; 
     bool counted = false; 

     switch (direction) { 
     case MOVE_T: 
      if ((row < n - 1) && (map[col][row] == map[col][row + 1])) 
       if (scanned[col][row + 1]) 
        counted = true; 
       else 
        count += scanTile(col, row + 1, MOVE_T, (0 < row) && (map[col][row] == map[col][row - 1])); 
      break; 
     case MOVE_B: 
      if ((0 < row) && (map[col][row] == map[col][row - 1])) 
       if (scanned[col][row - 1]) 
        counted = true; 
       else 
        count += scanTile(col, row - 1, MOVE_B, (row < n - 1) && (map[col][row] == map[col][row + 1])); 
      break; 
     case MOVE_R: 
      if ((col < n - 1) && (map[col][row] == map[col + 1][row])) 
       if (scanned[col + 1][row]) 
        counted = true; 
       else 
        count += scanTile(col + 1, row, MOVE_R, (0 < col) && (map[col][row] == map[col - 1][row])); 
      break; 
     case MOVE_L: 
      if ((0 < col) && (map[col][row] == map[col - 1][row])) 
       if (scanned[col - 1][row]) 
        counted = true; 
       else 
        count += scanTile(col - 1, row, MOVE_L, (col < n - 1) && (map[col][row] == map[col + 1][row])); 
      break; 
     default: 
      exit(ERR_MOVE); 
     }; 

     if ((opposite ? 1 : 0) + 1 + count + (counted ? 1 : 0) >= 3) { 
      switch (direction) { 
      case MOVE_T: 
      case MOVE_B: 
       temp = 0; 
       if ((col < n - 1) && !scanned[col + 1][row] && (map[col][row] == map[col + 1][row])) 
        count += temp = scanTile(col + 1, row, MOVE_R, (0 < col) && (map[col][row] == map[col - 1][row])); 
       if ((0 < col) && !scanned[col - 1][row] && (map[col][row] == map[col - 1][row])) 
        count += scanTile(col - 1, row, MOVE_L, temp ? true : false); 
       break; 
      case MOVE_L: 
      case MOVE_R: 
       temp = 0; 
       if ((row < n - 1) && !scanned[col][row + 1] && (map[col][row] == map[col][row + 1])) 
        count += temp = scanTile(col, row + 1, MOVE_T, (0 < row) && (map[col][row] == map[col][row - 1])); 
       if ((0 < row) && !scanned[col][row - 1] && (map[col][row] == map[col][row - 1])) 
        count += scanTile(col, row - 1, MOVE_B, temp ? true : false); 
       break; 
      default: 
       exit(ERR_MOVE); 
      }; 

      scanned[col][row] = true; 
      map[col][row] = 0; 
      return count; 
     } else { 
      return 0; 
     }; 
    }; 

public: 
    Jewel() : score(0) { 
     fileInput(); 
    }; 

    void process() { 
     outputMove(); 

     while (inputMove()) { 
      if (beginMove()) { 
       bool first = true; 

       while (scanMap()) { 
        outputMove(); 
        drop(); 
        outputMove(); 
        first = false; 
       }; 

       if (first) 
        revertMove(); 
      }; 

      outputMove(); 
     }; 

     fileOutput(); 
    }; 
};

來源

2014-04-01 Nguyễn Đức Long

+2

呃，這是無底的遞歸？或者不是真實的代碼？ –

+0

實際代碼非常複雜 –

+0

四月愚人永不復雜 – sehe

回答

1

堆棧和許多其他事物一樣，是有限大小的東西，隨着遞歸的使用，空間越來越多，直到用完爲止，程序進入溢出狀態。

在基於* nix的操作系統下，通常您可以使用命令ulimit -a或ulimit -s（較短的輸出）來獲取堆棧的大小，它在GNU/linux下通常爲7/8Mb左右。

來源

2014-04-01 13:49:29 user2485710

+0

你是對的，我想通了問題:) –

1

當你與遞歸工作，你必須有一個退出條件中發現的問題。

堆棧溢出通常發生在沒有一個堆棧時，或者當它太遠意味着遞歸太深時。

來源

2014-04-01 13:42:10 Geoffroy

+0

我真實的代碼有退出條件，我不擔心它 –

相關問題

 相關問題