Segmentation fault for numbers too big for Ackermann's function

Question

Why is this failing? I have written Ackermann's function in C and used longs to make sure that no number will be too small. Yet, when I go above (including) 4 for m and n, it gives me a segmentation fault: 11. Does anyone know why?

  #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

I have written Ackermann's function in C and used longs to make sure that no number will be too small.

The size of an unsigned long long is 2^6 (64) bits. The size of the result for ackermann(4, 2) is greater than 2^16 (65536) bits. You can compute ackermann(4, 1) and ackermann(5, 0) but not much with larger values of m and n.

Code-wise, you use a signed long when an unsigned long might serve you better and you declare the ackermann() function itself to return a signed int which is inconsistent. (Your ackermann() function also has a fourth exit point that isn't properly defined, compiler-wise.) Here's a rework of your code using unsigned long long which still won't get you very far:

#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;
}