Функция Ackermann's segfaults на gcc

Question

Будет ясно, что я не компетентный писатель C, но задавался вопросом в связи с этим вопросом Ackermann very inefficient with Haskell/GHC (что раздражает меня, возможно, иррационально), почему авторская программа для расчета знаменитой функции Вильгельма Аккермана:

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

работает отлично, но когда дал очевидную оптимизацию (которая помогает в другом месте) и учитывая аргумент (4,2) - что, конечно, алгоритмический жестоко - заканчивается Segmentation fault: 11:

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

Если я «оптимизирующая» линия if (m == 1) return n+2;, программа работает так же, как на других языках, но не имеет такого же эффекта - по крайней мере, после 5 минут работы. [Исправление, кажется, это - после того, как 8m41s] (следует отметить, что я использую GCC, которая поставляется с OS X, но то же самое, кажется, происходит с например gcc-4.7.2 на ideone.com.)

Я согласен программу не заслуживает даже компиляции, но задайтесь вопросом, почему ошибка сегментации, которая обычно рассматривается с ужасом и как ошибка языка или компилятора на других языках, с которыми я знаком, здесь является подходящим ответом для gcc.

Answer 1

Обе программы заканчиваются из стека, и ваше улучшение делает это быстрее. Имейте в виду, что требуемый стек пропорционален параметру «n», а «n» быстро растет. Так что никакой ошибки, просто ограниченная машина.

Позвольте мне добавить код из моего архива, просто для удовольствия и большей скорости. Также показано, как быстро растет число «n» с каждым приращением «m».

typedef unsigned long long N; 
N acker (N m, N n) 
{ 
     while (1) 
     switch (m) 
     { 
     case 0: return n+1U; 
     case 1: return n+2U; 
     case 2: return 2U*(n+1U)+1U; 
     case 3: return (1LLU<<(n+3U))-3U; 
     default: 
       if (n == 0U) 
         n = 1U; 
       else 
         n = acker(m, n-1U); 
       m--; 
       break; 
     } 
     return n+1U; 
}