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.

SUMMARY: AddressSanitizer: stack-overflow /tmp/so/p.cpp:29 in primality(unsigned long, unsigned long) — Stephen Newell
– Stephen Newell, Commented Oct 25, 2021 at 12:24
You exhausted your stack. Make your stack bigger. (How to do that varies by platform.) 3221225725 — Eljay
– Eljay, Commented Oct 25, 2021 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
– molbdnilo, Commented Oct 25, 2021 at 12:49

Markus Mayr · Accepted Answer · 2021-10-25 12:24:57Z

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, 2021 at 12:24

Markus Mayr

4,1081 gold badge23 silver badges42 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

JRBros Over a year ago

How can I solve this Problem?

Aconcagua Over a year ago

@JRBros i = 5; yet inside the if?

JRBros Over a year ago

It would cause an infinite loop that assigns 5 forever

Aconcagua Over a year ago

@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...

justANewb stands with Ukraine · Accepted Answer · 2021-10-25 13:19:10Z

1

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";
}

edited Oct 25, 2021 at 13:19

answered Oct 25, 2021 at 12:46

justANewb stands with Ukraine

4,6633 gold badges17 silver badges43 bronze badges

1 Comment

Aconcagua Over a year ago

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...

Collectives™ on Stack Overflow

How to stop crashes in a recursion loop

2 Answers 2

4 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related