使用长整数的 C 段错误

Question

我不明白为什么这段代码会编译然后出现段错误:

#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("%ld\n", 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)中使用适当的优化级别应该可以消除段错误。

幸运的是，迭代地编写这个非常简单:

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

  return a;
}