Stack overflow в рекурсивной функции(c++)

458
27 августа 2017, 04:57

Пишу сапёра на с++. Для хранения клеток использую двумерный динамический массив(позже планирую пользовательский ввод размера поля). Клетка представляет собой структуру. При нажатии на пустую клетку вызывается рекурсивная функция(shw), которая проверяет соседние клетки на пустоту, и если они пустые открывает их. При первом вызове функция работает как надо, но при рекурсивном вызове выдаёт:"Необработанное исключение по адресу 0x000329C9 в project.exe: 0xC00000FD: Stack overflow (параметры: 0x00000001, 0x00202F40)."

#include <iostream>
#include <ctime>
using namespace std;
int xy = 2;
int bombs = 1;
struct cell {
    bool bomb = false;
    int count = 0;
    bool show = false;
    bool flag = false;
    cell() {
        bomb = false;
    }
};
int calc(cell** ar, int x, int y) {
int sum = 0;
for (int i = -1; i < 2; i++) {
    for (int j = -1; j < 2; j++) {
        if (!(i == 0 && j == 0)) {
            if (x + i > -1 && y + j > -1 && x + i < xy && y + j < xy) {
                if (ar[x + i][y + j].bomb)
                    sum++;
            }
        }
    }
}
return sum;
}
void shw(cell** ar, int x, int y) {
    for (int i = -1; i < 2; i++) {
        for (int j = -1; j < 2; j++) {
            if (!(i == 0 && j == 0)) {
                if (x + i > -1 && y + j > -1 && x + i < xy && y + j < xy) {
                    if (!ar[x + i][y + j].bomb && !ar[x + i][y + j].flag) {
                        ar[x + i][y + j].show = true;
                        shw(ar, x + i, y + j);
                    }
                }
            }
        }
    }
}
void main()
{
    srand(time(0));
    int finds = 0;
    int shows = 0;
cell** field = new cell*;
for (int i = 0; i < xy; i++)
    field[i] = new cell[xy];
int rndx = 0, rndy = 0;
int temp = 0;
while (temp < bombs) {
    rndx = rand() % xy;
    rndy = rand() % xy;
    if (!field[rndx][rndy].bomb) {
        temp++;
        field[rndx][rndy].bomb = true;
    }
}
for (int i = 0; i < xy; i++) {
    for (int j = 0; j < xy; j++) {
        field[i][j].count = calc(field, i, j);
    }
}
for (int i = 0; i < xy; i++) {
    for (int j = 0; j < xy; j++) {
        if (!field[i][j].bomb)
            cout << field[i][j].count;
        else
            cout << "x";
        if (field[i][j].flag && !field[i][j].bomb)
            cout << "!";
    }
    cout << endl;
}
int mx = 0, my = 0;
bool flag = false;
while (!(finds == bombs || shows == (xy*xy - bombs))) {
    cout << "///////////////////////////////////////////////////////////////" << endl;
    for (int i = 0; i < xy; i++) {
        for (int j = 0; j < xy; j++) {
            if (field[i][j].show)
                cout << field[i][j].count;
            if (field[i][j].flag)
                cout << "!";
            if (!field[i][j].show && !field[i][j].flag)
                cout << "?";
        }
        cout << endl;
    }
    cin >> mx >> my >> flag;
    if (flag) {
        if (field[mx][my].show)
            field[mx][my].show = false;
        field[mx][my].flag = !field[mx][my].flag;
    }
    else {
        if (field[mx][my].bomb) {
            cout << endl << endl;
            for (int i = 0; i < xy; i++) {
                for (int j = 0; j < xy; j++) {
                    if (!field[i][j].bomb)
                        cout << field[i][j].count;
                    else
                        cout << "x";
                    if (field[i][j].flag && !field[i][j].bomb)
                        cout << "!";
                }
                cout << endl;
            }

            cout << "LOSE" << endl;
            system("pause");
            return;
        }
        else {
            field[mx][my].show = true;
            shw(field, mx, my);
        }
    }
    finds = 0;
    for (int i = 0; i < xy; i++) {
        for (int j = 0; j < xy; j++) {
            if (field[i][j].bomb && field[i][j].flag)
                finds++;
        }
    }
    shows = 0;
    for (int i = 0; i < xy; i++) {
        for (int j = 0; j < xy; j++) {
            if (field[i][j].show && !field[i][j].flag)
                shows++;
        }
    }
}
cout << "VICTORY!" << endl;
system("pause");
}
Answer 1

У вас очень глубокая рекурсия при очень низком потреблении памяти. Значит, проблема не в памяти, как таковой, а в неверной рекурсии.

Например, рекурсии без условия ее завершения.

Что будет при проверке клетки, из которой вы уже пришли? По коду - ничего. Вы ее откроете, но никак не дадите своей рекурсивной функции понять, что для нее рекурсию вызывать не нужно. Т.е. вы делаете бесконечную рекурсию... Рекурсия всегда подразумевает проверку условия, что далее она не нужна - иначе жди проблем...

Типа - пойдем вправо. Откроем. Теперь рекурсивно пойдем влево. Откроем. Дальше - рекурсивно пойдем вправо... Ну, вы поняли, да?

READ ALSO
Массив из булевых переменных

Массив из булевых переменных

Я хочу сделать так, что бы некоторый набор элементов в массиве при запуске имел значение trueВ дальнейшем, когда пользователь занимает какую...

454
Чтение .dwg файлов в проекте на c++/c#

Чтение .dwg файлов в проекте на c++/c#

Ребята, приветствуюСтолкнулся с такой проблемой: есть

306
Error в ajax запросе и статус 200

Error в ajax запросе и статус 200

В моей функции выполняется ajax запрос:

302
jQuery.click срабатывает сам при загрузке

jQuery.click срабатывает сам при загрузке

Здравствуйте! Возникла проблемаПри загрузке страницы автоматически сам по каким-то причинам срабатывает click

243