How to stop crashes in a recursion loop

Question

I made this simple function, but it crashes at p=29. It makes a stopped working error window. Please Help Me

#include <iostream>
using namespace std;

char *primality(unsigned long,unsigned long i=0);

int main()
{
    for(int i=0;i<1000;i++)
        cout<<i<<": "<<primality(i)<<endl;
};

char *primality(unsigned long p,unsigned long i)
{
    if(i==0)
    {
        if(p<=1)
            return "NEITHER PRIME NOR COMPOSITE";
        else if(p==2||p==3)
            return "\tPRIME";
        else if(p%2==0||p%3==0)
            return "\tCOMPOSITE";
    }
    i=5;
    if(i*i<=p)
        if(p%i==0||p%(i+2)==0)
            return "\tCOMPOSITE";
        else
            return primality(p,i+6);
    else
        return "\tPRIME";
}

The output after 29 is stopped and causes a crash Output:

0: NEITHER PRIME NOR COMPOSITE
1: NEITHER PRIME NOR COMPOSITE
2:      PRIME
3:      PRIME
4:      COMPOSITE
5:      PRIME
6:      COMPOSITE
7:      PRIME
8:      COMPOSITE
9:      COMPOSITE
10:     COMPOSITE
11:     PRIME
12:     COMPOSITE
13:     PRIME
14:     COMPOSITE
15:     COMPOSITE
16:     COMPOSITE
17:     PRIME
18:     COMPOSITE
19:     PRIME
20:     COMPOSITE
21:     COMPOSITE
22:     COMPOSITE
23:     PRIME
24:     COMPOSITE
25:     COMPOSITE
26:     COMPOSITE
27:     COMPOSITE
28:     COMPOSITE
29:
--------------------------------
Process exited after 2.855 seconds with return value 3221225725
Press any key to continue . . .

Also, note that I got a return value. Please tell the meaning of this error message

I'm also instructed to use char arrays instead of strings.

Does this answer your question? [stack overflow c++](https://stackoverflow.com/questions/14182127/stack-overflow-c) — Stephen Newell, Oct 25 '21 at 12:24
`SUMMARY: AddressSanitizer: stack-overflow /tmp/so/p.cpp:29 in primality(unsigned long, unsigned long)` — Stephen Newell, Oct 25 '21 at 12:24
You exhausted your stack. Make your stack bigger. (How to do that varies by platform.) [3221225725](https://james.darpinian.com/decoder/?q=3221225725) — Eljay, Oct 25 '21 at 12:36
You are ignoring any non-zero value of `i`, and you have the equivalent of `if(25<=p) if(p%5==0||p%7==0) return "\tCOMPOSITE"; else return primality(p, 11);`, which is pretty clearly not correct. — molbdnilo, Oct 25 '21 at 12:49
@Eljay Just a little insight as late addition (admitted): Increasing stack size wouldn't help due to endless recursion. Seems, though, as the programme was compiled without (sufficiently high level of) optimisations, as actually the function could have been tail-call-optimised – with result of endless recursion without stackoverflow. — Aconcagua, Oct 26 '21 at 10:24
@JRBros There are a few other issues with your code, by the way: 1. about [`using namespace std`](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice). 2. You do return string literals, these are of type `char const[]`, and you absolutely should retain constness by returning `char const*` from your function (didn't you get a compiler warning? if not, increase warning level!). — Aconcagua, Oct 26 '21 at 10:36

score 4 · Answer 1 · answered Oct 25 '21 at 12:24

4

29 is the first number, for which you enter into an endless recursion. As a consequence, the application crashes eventually.

I did not look at your algorithm in much detail, but I assume that i=5 is not really working as expected.

answered Oct 25 '21 at 12:24

Markus Mayr

4,038
1
20
42

How can I solve this Problem? – JRBros Oct 25 '21 at 12:29
@JRBros `i = 5;` yet *inside* the `if`? – Aconcagua Oct 25 '21 at 12:34
It would cause an infinite loop that assigns 5 forever – JRBros Oct 25 '21 at 12:36
1

@JRBros There's no loop at all, suppose you mean recursion – but that's what you have *now*. If you move the assignment inside the `if` as very last action `if(i == 0) { /*...*/; i = 5; }` then you check (assuming `p` is large enough, i.e. >= 25) for 5 and 7 and recurse for the first time with 11, checking with 11 and 13 and again recurse with 17... – admitted, the code still could be written more nicely, but at least that solves the issue... – Aconcagua Oct 26 '21 at 12:02

justANewb stands with Ukraine · Accepted Answer · 2021-10-25T13:19:10.100

In your primality() function,


char *primality(unsigned long p,unsigned long i)
{
    if(i==0)
    {
        if(p<=1)
            return "NEITHER PRIME NOR COMPOSITE";
        else if(p==2||p==3)
            return "\tPRIME";
        else if(p%2==0||p%3==0)
            return "\tCOMPOSITE";
    }
    i=5;
    if(i*i<=p)
        if(p%i==0||p%(i+2)==0)
            return "\tCOMPOSITE";
        else
            return primality(p,i+6);
    else
        return "\tPRIME";
}

You're assigning the value 5 to i every time primality() runs. So the recursion has no stop. Eventually, your stack is too tired to hold all the different primality() calls, it will cause a stack overflow.

Change that to:

char *primality(unsigned long p,unsigned long i = 5);

char *primality(unsigned long p,unsigned long i)
{
    if(p<=1)
        return "NEITHER PRIME NOR COMPOSITE";
    else if(p==2||p==3)
        return "\tPRIME";
    else if(p%2==0||p%3==0)
        return "\tCOMPOSITE";

    if(i*i<=p)
        if(p%i==0||p%(i+2)==0)
            return "\tCOMPOSITE";
        else
            return primality(p,i+6);
    else
        return "\tPRIME";
}

In contrast to original solution (assumed being fixed as in comments to other answer) this variant has some disadvantage, though: Original solution needs one single test in recursion, this one repeats the whole set of tests before `if(i*i <= p)` – which are obsolete in all recursive calls... — Aconcagua, Oct 26 '21 at 10:19

How to stop crashes in a recursion loop

2 Answers2