Dia C - Recursão

Recursão é um assunto bem complexo. Aqui, não camos entrar nas questões sobre o design de algoritmos recursivos ou como uma solução recursiva pode ser melhor ou pior que uma solução iterativa. O ponto que será tratado aqui é a relação da recursão com a pilha do C.

Como já sabem, quando uma função é carregada, os parâmetros dela são alocados na pilha. Isso significa que parte da memória é consumida. Como a pilha tem aproximadamente 8mb, isso aparentemente não é um problema. Mas é. Realmente, se você utilizar pouca recursão, não existe problema algum pois será muito difícil estourar a pilha. Mas se várias funções do seu sistema estão implementadas de forma recursiva (especialmente se ocorrer alguma espécie de recursão aninhada, como quando percorremos recursivamente uma árvore de árvores), isso é um problema sério.

Como geralmente é difícil prever até onde a função irá descer recursivamente, é muito difícil encontrar um erro causado por estouro de pilha. Especialmente porque é lançada uma falha de segmentação, o que não quer dizer muita coisa pois vai desde acesso à ponteiro NULL a aceeso fora do limite de um vetor ou várias outras coisas.

Estou desencorajando voc&es a utilizarem recursão? De jeito nenhum. Recursão é uma técnica fantástica (eu sou fascinado por recursão) que possibilita soluções simples e elegantes, mas ela deve ser usada de forma correta.
É importante evitar usar recursão em lugares em que é simples trocá-la por um laço. Deve-se evitar recursões aninhadas, pois tem uma capacidade incrível de consumir a pilha. E evitar funções recursivas com muitos parâmetros ou com parâmetros muito grandes (a pilha será consumida muito mais rápido).

Portanto usem e abusem de recursão. E não se preocupem com preconceitos como “A recursão deixa o programa mais lento”. É verdade que existe um gasto maior de processamento, mas é tão pequeno que com os processadores atuais ele pode ser desconsiderado. Isso é apenas uma desculpa de programadores que não conseguem escrever algoritmos recursivos.

Maiores informações: recursão -> Google, recursão -> Wiki.

Próxima semana, Threads em C.