Как манипулирование массивом символов вызывает переполнение стека? - PullRequest
Новая
       8

Как манипулирование массивом символов вызывает переполнение стека?

0 голосов
/ 09 ноября 2018

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

Я знаю, что массивы являются указателями, но может ли изменение значения вызвать переполнение стека?

Вот соответствующая функция: 

char base[] = "aaaaa";
void changeLetters(int position) { // Stack overflow happens around here
    if (base[position] != 'z') {
        base[position]++;
    }

    // When I include a cout here, I also get a stack overflow

    if (position == 4 && base[position] != 'z') {
        changeLetters(position);
    }
    else if (base[position] == 'z' && position != 0) {
        base[position] = 'a';
        changeLetters(position - 1);
    }
    else if (position < 4) {
        changeLetters(position + 1);
    }
}

Если у меня нет std::cout, я получаю

Необработанное исключение в 0x767C3210 (KernelBase.dll) в passwordCracker.exe: 0xC00000FD: переполнение стека (параметры: 0x00000001, 0x01002FFC).

В противном случае

Необработанное исключение в 0x009C38B9 в passwordCracker.exe: 0xC00000FD: переполнение стека (параметры: 0x00000001, 0x006D2F8C).

Edit: Функция вызывается в основном цикле. Переданное значение - это длина строки (4), и она проходит через нее. Одна странная вещь, которую я не упомянул, это то, что она отлично работает, если я перебираю меньшее количество букв (a, b, c, d), но я получаю переполнение стека, только если у меня есть цикл по алфавиту.

Ответы [ 2 ]

0 голосов
/ 09 ноября 2018

Рекурсия не бесконечна, но она глубока. Достаточно глубоко, чтобы взорвать стек.

Функция использует рекурсию каждый раз, когда увеличивает букву. И поскольку есть 5 символов, каждый из которых содержит 26 возможных значений, рекурсия имеет глубину 26 5 = 11881376 уровней. Я не уверен, насколько велик ваш стек, но он недостаточно велик, чтобы справиться с таким количеством уровней. Таким образом, вы получаете переполнение стека.

Переключиться на итеративное решение с использованием вложенных циклов.

0 голосов
/ 09 ноября 2018

Ваш код перебирает все строки длины 5, состоящие из алфавита a-z. Само по себе это не проблема, однако вы должны убедиться, что максимальная глубина вызова не слишком велика.

На каждой итерации changeLetters вы увеличиваете не более одной буквы один раз, а затем снова вызываете changeLetters и делаете не более одного такого вызова.

Таким образом, ваш график вызовов является полностью линейным, для каждой из строк 26^5 вы делаете еще один рекурсивный вызов в глубину, и поэтому стек вызовов в конце будет примерно таким большим. Проблема в том, что это очень большое число 26^5 = 11881376 и может легко превышать пространство стека, которое вы можете использовать.

Вам необходимо превратить линейный граф вызовов в один с ветвями, например, например. используя цикл над текущей позицией персонажа вместо вызова changeLetters каждый раз.

...