C++ Stack Overflow while using recursive function

Question

I have a class which has recursive function. I tested 100 cases and the code works fine. However, I ran another test and, after a few recursive call, received a First-chance Exception showing about stack overflow, I chose to ignore it and then an unhandled exception shown up about memory reading violation.

Assume that I have the following code (not the real code, which has exit condition):

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

When I use debugger, I find that at the time Bar is called, the this pointer receives the wrong address number, causing the reading of the Foo object wrong and I don't know why.

Does anyone know about that?

Or should I try?

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

EDIT

Here is the real code that is used to simulate the game Jewel. I found problem at the scanTile method

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();
    };
};

Answer 1

The stack, as many other things, is something with a finite size and with your recursion you are using more and more space until you run out and your program goes in overflow.

under *nix based OSs usually you can use the command ulimit -a or ulimit -s ( shorter output ) to get the size of the stack, which under a GNU/linux distribution is usually around 7/8Mb .

Answer 2

When you work with recursion, you must always have an exit condition.

Stack overflows generally happen when you don't have one, or when it is too far meaning your recursion is too deep.