为什么我的递归函数seg在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; 
} 

我明白，递归通常只到一定的深度。但据我所知，我已经实现了尾部递归，它应该能够阻止seg故障。如果我将我设置为100,000，程序运行将导致我相信底层算法是正确的。但是一百万，我得到：

分段故障：11

我在做什么错？

Answer 1

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

Answer 2

如果你是100万运行它，我会说你很可能只是运行的堆栈空间不足引起段错误

什么编译/ OS是你使用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); 
    } 
}