Блог

Привет, практикуясь в рекурсии, я нашел упражнение для поиска модулей без использования оператора%. Итак, я написал свою функцию, и все работает нормально. За исключением случаев, когда я набираю числа из 5 цифр или более, эта функция завершается с ошибкой. И я не уверен, делаю ли я что-то неправильно или это сбой, потому что слишком много вызовов. Если вызовов слишком много, это нормально? Действительно ли может быть слишком много вызовов функций? Как я могу предотвратить это, если в будущем у меня будет функция рекурсии, которая действительно полезна? Потому что для меня это не имеет смысла на самом деле. Я выполнил рекурсию ханойской башни, и у нее никогда не возникало этой проблемы, независимо от того, сколько дисков я хочу переместить.

Вот моя функция, а также предпосылка, что оба числа всегда положительны:

 #include <iostream>

using namespace std;
int modulo(int n, int m) {
    if (n < m) return n;
    else return modulo(n - m, m);
}

int main()
{
    int n{ 0 }, m{ 0 };
    char check{ 'a' };
    do {
        cout << "Enter 2 positive integers to calculate their modulo: ";
        cin >> n >> m;
        if (cin.fail()) {
            cerr << "Numbers must be a positive integers. Please try again.n";
            cin.clear(); //clear input stream
            cin.ignore(std::numeric_limits<std::streamsize>::max(), 'n'); //discard any unprocessed characters
        }
        else if (n < 0 || m <= 0) {
            cerr << "Numbers must be positive and second number cannot be zero.nPlease try again.n";
        }
        else {
            cout << "n%m = " << n << "%" << m << " = " << modulo(n, m) << endl;
            cout << " Try again? (enter 'n' to quit): ";
            cin >> check;
        }
    } while (check != 'n');
}
  

Ошибка заключается:

Необработанное исключение в 0x00007FF77D5C2793 в GuessNumber.exe: 0xC00000FD: Переполнение стека (параметры: 0x0000000000000001, 0x0000006F322F3F30).

для чисел, которые я пробовал 40001% 10, это работает, но 44001% 10 терпит неудачу, и все, что после 44001, также терпит неудачу для меня. я не пробовал никаких других чисел

Если рекурсия слишком глубока, то программе не хватает стековой памяти. Это называется Stack Overflow.

 int modulo(int n, int m) 
{ 
    if (n < m) return n; 
    else return modulo(n - m, m); 
}
  

Например, modulo(1000000, 2) вызывает modulo(999998, 2) , который вызывает modulo(999996, 2) , и так далее, пока modulo(0, 2) в конце в стеке не останется 500001 активных modulo функций. Два целых числа, адрес возврата и указатель фрейма должны занимать не менее 16 байт на вызов функции в любой разумной системе. Всего 8 мегабайт стекового пространства, что обычно превышает максимальный размер стека.

Каждый вызов функции должен ждать результатов следующей функции, пока она не сможет завершить свое вычисление и вернуть результат. До тех пор, пока он не вернет, стек должен был содержать все переменные, параметры и обратный адрес. Адрес возврата — это местоположение в программе, где программа должна возобновиться после return инструкции.

Эти вызовы заполняют стек до тех пор, пока не будет достигнут его максимальный предел и программа не завершится сбоем.

В некоторых случаях компилятор может преобразовать рекурсию в цикл. В этом случае, поскольку рекурсия выполняется в return инструкции, она может просто goto перейти к началу функции, вообще не выполняя вызов. Это называется оптимизацией конечных вызовов:

 int modulo(int n, int m) 
{ 
    start:
    if (n < m) return n; 
    else {
       n -= m;
       goto start;
    }
}
  

Если бы вы включили оптимизацию (-O2 в clang или G , или release mode на Visual C ), сбоя бы не произошло, поскольку компилятор создал бы цикл вместо рекурсии. Чтобы избежать сбоя, просто включите оптимизацию.

Обратите внимание, что компилятор не обязан оптимизировать это, и он не всегда может. Вот почему не рекомендуется проводить такую глубокую рекурсию.

Вы выполняете рекурсию на глубину 4400, что создает проблемы. Также здесь в этом нет необходимости, потому что вы можете реализовать тот же алгоритм с циклом:

 while (n >= m) n -= m ;
return n ;