title: Ackermann's function segfaults on gcc
body: <p>It will be plain I am not a competent writer of C, but was wondering, in connection with this question <a href="https://stackoverflow.com/questions/16115815/ackermann-very-inefficient-with-haskell-ghc">Ackermann very inefficient with Haskell/GHC</a> (which irritating me perhaps irrationally) why the author's program to calculate Wilhelm Ackermann's famous function:</p>
  
  <pre><code>int ack(int m, int n) {
    if (m == 0) return n+1;
    if (n == 0) return ack(m-1, 1);
    return ack(m-1, ack(m, n-1));
  }
  
  int main() {
    printf("%d\n", ack(4,1));
    return 0;
  }
  </code></pre>
  
  <p>works fine, but when given an obvious optimization (which helps elsewhere) and given the argument (4,2) -- which is of course algorithmically cruel -- ends with <code>Segmentation fault: 11</code> : </p>
  
  <pre><code>int ack(int m, int n) {
    if (m == 0) return n+1;
    if (m == 1) return n+2;
    if (n == 0) return ack(m-1, 1);
    return ack(m-1, ack(m, n-1));
  }
  
  int main() {
    printf("%d\n", ack(4,2));
    return 0;
  }
  </code></pre>
  
  <p>If I comment out the 'optimizing' line <code>if (m == 1) return n+2;</code>, the program runs on and on as it does in other languages, but doesn't have the same effect -- at least not after say 5 minutes of operation. [Correction, it seems it does -- after 8m41s] (I should note that I am using gcc that comes with os x, but the same seems to be happening with e.g. the <code>gcc-4.7.2</code> on <code>ideone.com</code>.) </p>
  
  <p>I agree the program doesn't deserve even to be compiled, but wonder why a segmentation fault, which is generally viewed with horror and as a language flaw or compiler fault in other languages I am familiar with, is here the appropriate response for the <code>gcc</code> .  </p>