Pilha e Estouro de Pilha

Recursão tem uma desvantagem: há um limite no número de níveis aninhados de chamadas de função que um programa pode fazer. Em C, cada chamada de função aloca um bloco de memória que é utilizado até que a chamada retorne. A linguagem C aloca estes blocos consecutivamente numa grande área de memória conhecida como pilha (stack), portanto chamamos este blocos de quadros de pilha (stack frames).

O tamanho da pilha é limitado; se um programa tenta usar muito dela, isso causa uma falha porque a pilha estará cheia. Isso é chamado de estouro de pilha (stack overflow).

Estouros de pilha no GNU/Linux se manifestam tipicamente como o sinal chamado de SIGSEGV, também conhecido como "falha de segmentação" ("segmentation fault"). Por padrão, este sinal encerra a execução do programa imediatamente ao invés de permitir que o programa se recupere ou atinja seu fim esperado. (Nestes casos, nós normalmente falamos que o programa "crashou"). Veja Sinais.

Não é conveniente tentar observar um estouro de pilha passando um número grande como argumento para uma função recursiva que implemente Fibonacci porque o programa rodaria por muito tempo antes de dar erro. O algoritmo é simples, mas lentíssimo: ao calcular fib (n), o número de chamadas (recursivas) fib (1) ou fib (2) que ele vai fazer é igual ao resultado final.

Todavia, você pode rapidamente observar um estouro de pilha usando seguinte função:

int
fill_stack (int n)
{
  if (n <= 1)  /* Limita a profundeza da recursão  */
    return 1;
  else
    return fill_stack (n - 1);
}

Com um laptop Lemote Yeeloong rodando o sistema operacional gNewSense GNU/Linux com configuração padrão, um experimento demonstrou que há espaço suficiente na pilha para realizar 261906 chamadas aninhadas para essa função. Uma mais e a pilha estoura e o programa é encerrado. Em outra plataforma com uma configuração diferente ou com uma função diferente, o limite pode ser maior ou menor.