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 .
Aqui me rendi ao neologismo "crashou", oriundo do inglês "crash". Até pensei em usar "travou", mas este termo nós brasileiros normalmente utilizamos quando o programa para de responder ("congela"), mas numa situação de estouro de pilha, o programa é encerrado e não fica "congelado" ou "travado".
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:
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.
Em meus testes com o Windows 11 e Visual Studio 2022, a pilha estourou a partir de 4023 chamadas, ou seja, com fill_stack(4024)
.
Atualizado