c - 为什么我的递归函数在 C 中会出现段错误？

Question

我的程序如下：

#include <stdio.h>

int collatz(int seed, int count) {
    int next = 0;
    if (seed % 2 == 0) {
        next = seed / 2;
    } else {
        next = 3 * seed + 1;
    }
    count++;
    if (next == 1) {
        return count;
    } else {
        return collatz(next, count);
    }
}

int main() {
    int max = 0;
    int index = 0;
    int i;
    for (i=1; i<1000000; i++) {
        int current = collatz(i, 1);
        if (current > max) {
            max = current;
            index = i;
        }
    }
    printf("%i\n", index);
    return 0;
}

我知道递归通常只会达到一定的深度。但是据我所知，我已经实现了尾递归，它应该可以停止段错误。如果我将 i 设置为 100,000，程序就会运行，这让我相信底层算法是正确的。然而，在一百万我得到：

分段错误：11

我究竟做错了什么？

Answer 1

如果您使用调试器，您可能会发现您的函数确实不是尾递归的。但为什么不呢？可能是因为您只是忘记在编译期间启用优化。在我的系统上（Mac OS 上的 GCC），默认构建会崩溃，但使用该-O3选项构建会让它运行（至少比其他方式运行更长的时间；我不想终止我的电池测试）。

Answer 2

如果你用 100 万运行它，我会说你可能只是用完了堆栈空间导致了段错误

您在 VS 堆栈大小中使用的编译器/操作系统默认为 1MB，但可以增加。我不确定其他编译器/操作系统组合

Answer 3

collat​​z函数在计算过程中导致溢出。（这是堆栈溢出）。

注意：尾递归的编译器优化可能会也可能不会。

使用 long long (Int64)。

int collatz(long long seed, int count) {
    long long next = 0;
    if (seed % 2 == 0) {
        next = seed / 2;
    } else {
        next = 3 * seed + 1;
    }
    count++;
    if (next == 1) {
        return count;
    } else {
        return collatz(next, count);
    }
}