使用长整数的C segfault

Question

我不明白为什么这段代码会编译，然后segfault：

#include <stdio.h>
#include <stdlib.h>
unsigned long int gcd(unsigned long int, unsigned long int);
unsigned long int lcm(unsigned long int, unsigned long int);
int main(int argc, char *argv[]) {
    int i;
    unsigned long int n = 1L;
    for (i = 2; i < 21; i++) {
        n = lcm(n, i);
    }
    printf("%ldn", n);
    return 0;
}
unsigned long int gcd(unsigned long int a, unsigned long int b) {
    if (a == b) return a;
    if (a > b) return gcd(a - b, b);
    return gcd(a, b - a);
}
unsigned long int lcm(unsigned long int a, unsigned long int b) {
    return abs(a * b) / gcd(a, b);
}

这些unsigned long甚至是必要的吗？我还注意到，如果我将21更改为18，它将给出正确的结果。该代码用于查找从1到20的所有数字的LCM。

在gdb中运行它给出：

Program received signal SIGSEGV, Segmentation fault.
0x0000000000400643 in gcd (a=7536618, b=18) at p5.c:19
19    if (a > b) return gcd(a - b, b);

Answer 1

您正在溢出堆栈。这是一个遗憾，因为这应该很容易被优化为尾部递归，完全递归在这方面是非常过分的。在任何现代编译器（cl、gcc、icc）中使用适当的优化级别都应该消除segfault。

幸运的是，反复地写这篇文章是微不足道的：

unsigned long gcd(unsigned long a, unsigned long b) 
{ 
  while(a != b)
    if(a > b)
       a -= b;
    else 
       b -= a;
  return a;
}

Answer 2

由于堆栈的工作方式以及它们的工作方式，函数调用的嵌套深度受到限制，这取决于它们保持的本地状态。

对于极不平衡的参数，通过重复减法实现gcd需要多次迭代，因此您的递归将深入。您需要更改实现（例如使其迭代），或者更改算法（例如计算余数而不是差值）。

您可以增加堆栈大小，但这会浪费内存，而且较大的大小最终也会随着较大的输入而耗尽。