C++递归素数计数程序传入大区间参数时崩溃原因

原程序实现代码如下：

#include <iostream>

using namespace std;
bool is_prime(int num , int cnt = -1){
    if(cnt == -1)
        cnt = num-1;

    if(num <= 1)
        return false;

    if(cnt == 1)
        return true;

    if(num % cnt == 0)
        return false;

    return is_prime(num , cnt-1);

}

int count_primes(int start , int end){
    if(start>end)
        return 0;
    if(is_prime(start))
        return 1 + count_primes(start+1 , end);
    else
    return 0 + count_primes(start+1 , end);
}
int main()
{
    cout<<count_primes(10 , 200);

    return 0;
}

直接崩溃原因：栈溢出 #

程序两处递归逻辑在大参数下会耗尽操作系统分配给进程的默认栈空间，触发内存访问违规崩溃：

• count_primes采用递归写法遍历区间，每递归一次处理一个数，递归总深度等于区间长度。传入10到5000000的参数时，仅这个函数的递归深度就接近500万层。每一层函数调用都要在栈上存储返回地址、函数参数、栈帧寄存器数据，单这部分占用就远超默认栈大小（Windows默认栈大小1MB，Linux默认通常8MB，仅能支撑几千到几万层普通函数调用）。
• is_prime判断素数也采用递归实现，判断数值num时，递归从num-1逐次减1直到1，递归深度等于num-2。哪怕外层不做区间遍历，单次判断5000000这个数是否为素数，就会产生近500万层递归，直接把栈空间占满。

小区间场景下总递归深度最多几十层，栈占用远低于系统阈值，所以可以正常运行。

额外说明：即便把递归改写为迭代解决栈溢出问题，当前素数判断的逻辑效率也极低——从num-1开始逐次取模判断的时间复杂度为O(n)，遍历到500万时总运算量会达到万亿级别，程序会长时间占用CPU无法输出结果，实际使用需要把素数判断优化到O(√n)复杂度，或者改用埃氏筛、欧拉筛这类线性筛法实现区间计数。

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