c - 对于 Ackermann 函数而言，数字太大的分段错误

Question

为什么会失败？我用 C 语言编写了 Ackermann 的函数，并使用 long 来确保数字不会太小。然而，当我对 m 和 n 超过（包括）4 时，它给了我一个segmentation fault: 11. 有谁知道为什么？

  #include <stdio.h>

  int ackermann(long m, long n) {
      if (m == 0)
              return n + 1;
      else if (m > 0 && n == 0)
              return ackermann(m - 1, 1);
      else if (m > 0 && n > 0)
              return ackermann(m - 1, ackermann(m, n - 1));
  }

  int main() {
          long result = ackermann(4, 4);
          printf("%lu", result);
  }

Answer 1

我用 C 语言编写了 Ackermann 的函数，并使用 long 来确保数字不会太小。

an 的大小unsigned long long为 2^6 (64) 位。结果的大小ackermann(4, 2)大于 2^16 (65536) 位。您可以计算ackermann(4, 1)和ackermann(5, 0)但不能用更大的值m和n。

在代码方面，当无符号可能更好地为您服务并且您声明函数本身返回不一致时，您使用有符号。 （您的函数还有第四个退出点，但在编译器方面没有正确定义。）这是您的代码的返工，使用它仍然不会让您走得太远：long longackermann()signed intackermann()unsigned long long

#include <stdio.h>

unsigned long long ackermann(unsigned long long m, unsigned long long n) {
    if (m == 0) {
        return n + 1;
    }

    if (m > 0 && n == 0) {
        return ackermann(m - 1, 1);
    }

    return ackermann(m - 1, ackermann(m, n - 1));
}

int main() {
    unsigned long long result = ackermann(5, 0);
    printf("%llu\n", result);

    return 0;
}