C ++ рекурсия с большими числами, чтобы найти мод

Question

Привет, во время практики рекурсии, я нашел упражнение, чтобы найти модули без использования оператора%. Поэтому я написал свою функцию, и все работает отлично. За исключением случаев, когда я нажимаю цифры с 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, мне тоже не удалось. я не пробовал другой номер

Answer 1

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

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 ++ или режим релиза в Visual C ++), не было бы сбоя, так как компилятор создал бы цикл вместо рекурсии. Чтобы избежать сбоя, просто включите оптимизацию.

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

Answer 2

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

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