移除Collatz函数末尾if语句后出现Segmentation Fault问题求助

问题背景 #

我实现了一个计算Collatz序列最长长度的程序，代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>
#define max 100000000
int64_t table[max];
int64_t collatz(int64_t a);
int main(int argc,char*argv[])
{
    if (argc !=3)
    {
        printf("ERROR\nUsage: ./collatz {argv1} {argv2}\n");
        return 1;
    }
    int64_t maxlen = 0;
    int64_t num1 = atoi(argv[1]);
    int64_t num2 = atoi(argv[2]);
    if (num1 < 1 || num2 < 1 || num1 > max || num2 > max)
    {
        printf("%"PRId64"\n",maxlen);
        return 2;
    }
    int64_t i;
    for (i=num1;i<=num2;i++)
    {
        int64_t len = collatz(i);
        if (len > maxlen)
        {
            maxlen = len;
        }
    }
    printf("%" PRId64 "\n", maxlen);
    return 0;
}
int64_t collatz(int64_t a)
{
    if (a <= max)
    {
        if(table[a] != 0)
        {
            return table[a];
        }
    }
    int64_t len = 1;
    if (a != 1)
    {
        if (a%2==0)
            len += collatz(a/2);
        else
            len += collatz(a*3+1);
    }
    if (a <= max)
    {
        table[a]=len;
    }
    return len;
}

移除collatz函数中最后一段判断a <= max后给table[a]赋值的语句后，程序出现了Segmentation Fault（段错误）。我无法理解：数组table大小是100000000，主程序传入的参数都不会超过这个值，虽然递归计算时数值可能超出限制（比如99999999计算后会超出），但大于100000000的数值本来就不会触发被移除的那个if语句，为什么移除后会出问题？

原因分析 #

问题出在栈溢出，而非直接访问table数组越界。

原代码里，当a <= max时会把计算出的len存入table做缓存，后续再遇到同一个a时直接返回缓存值，不会继续递归。但移除缓存赋值语句后，所有递归调用都无法复用之前的计算结果，导致递归深度急剧增加。

比如计算接近1e8的奇数时，Collatz序列会产生大量中间值，而且每个值都会触发重复的递归调用——因为没有缓存，每次遇到同一个数都要重新走一遍递归流程。递归调用会不断占用栈空间，当递归深度超过程序允许的栈大小上限时，就会触发栈溢出，表现为段错误。

你之前误以为段错误是访问table越界导致的，但实际上移除缓存后，递归层数暴涨才是元凶。原有的缓存机制大幅减少了递归次数，避免了栈溢出；失去缓存后，递归深度直接突破栈的承载能力，最终引发段错误。

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