如何解决C++递归素数检测函数运行到p=29时崩溃的问题

• 递归逻辑错误：primality函数中存在无条件将i赋值为5的代码，覆盖了递归调用时传入的递增i值。当p=29时，每次递归i都会被重置为5：5*5=25≤29，且29无法被5或7整除，会无限触发primality(p, 11)调用，最终导致栈溢出。
• 错误返回值3221225725转换为十六进制为0xC00000FD，是Windows系统下的STATUS_STACK_OVERFLOW错误码，代表进程栈空间被耗尽，被系统强制终止。

要求使用char数组而非string类型，我们直接返回静态存储区的char数组字符串字面值（字符串字面值本身为const char[]类型，符合char数组要求，且生命周期覆盖整个程序运行周期，不会出现野指针问题）。修复后的完整代码如下：

#include <iostream>
using namespace std;

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

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

const 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，递归调用时不覆盖i的值
        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";
}

如果业务要求必须返回非const的char*，可以将返回的字符串定义为静态char数组，实现如下：

#include <iostream>
using namespace std;

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

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

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

内容的提问来源于stack exchange，提问作者JRBros