CODEWITHSUNDEEP
c++recursionmodulo
Artem Khizhnyak
Artem Khizhnyak

Reputation: 3

c++ recursion with big numbers to find mod

Hi while practicing recursion I found an exercise to find modulos without using the % operator. So I wrote my function and everything works fine. Except when I hit numbers with 5 digits or more this function fails. And I'm not sure whether I'm doing something wrong or it fails because there are too many calls. If there are too many calls, is it normal? Can there really be too many function calls? How can I prevent it from ever happening if in the future I have a recursion function that is actually useful? Because it doesn't make sense to me really. I did the tower of Hanoi recursion and it never has this problem, no matter how many disks I want to move.

Here's my function and the premise also that both numbers are always positive:

#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');
}

The error is:

Unhandled exception at 0x00007FF77D5C2793 in GuessNumber.exe: 0xC00000FD: Stack overflow (parameters: 0x0000000000000001, 0x0000006F322F3F30).

for the numbers i tried 40001 % 10, it works but 44001 % 10 fails and everything past 44001 fails for me also. i haven't tried any other number

Upvotes: 0

Views: 680

Answers (2)

TonyK
TonyK

Reputation: 17124

You are recursing to a depth of 4400, which is asking for trouble. Also it's unnecessary here, because you can implement the same algorithm with a loop:

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

Upvotes: 0

Michael Veksler
Michael Veksler

Reputation: 8475

If the recursion is too deep, then the program runs out of stack memory. It is called Stack Overflow.

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

For example, modulo(1000000, 2) calls modulo(999998, 2), which calls modulo(999996, 2), and so on until modulo(0, 2) at the end there are 500001 active modulo functions on the stack. Two integers, return address, and a frame pointer, should take at least 16 bytes per function call on any reasonable system. In total 8 megabytes of stack space, which is usually above the maximum stack size.

Each function call has to wait for the results of the next function, until it can complete its calculation and return. Until it returns the stack had to hold all variables, parameters, and the return address. The return address is the location in the program of where the program should resume after a return statement.

These calls fill up the stack, until its maximum limit is reached and the program crashes.

In some cases, the compiler can convert recursion into a loop. In this case, since the recursion is at the return statement, it can simply goto to the beginning of the function, without performing a call at all. This is called tail call optimization:

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

Had you enabled optimization (-O2 in clang or G++, or release mode on Visual C++) there would have been no crash since the compiler would have created a loop instead of recursion. To avoid the crash, simply enable optimizations.

Note that the compiler is not required to optimize this, nor it always can. That's why it is not advisable to have such a deep recursion.

Upvotes: 2

Related Questions