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.

Posts Relacionados:

Acompanhe-nos por RSS, por Email ou via Twitter.
Veja como ter um desconto no Dreamhost: um excelente servidor web.

O CodeIDE é uma ferramenta incrivel. Ele fornece pelo site a possibilidade de rodar várias linguagens de programação, como o Basic, Pascal, C++ (e consequentemente C), Perl, JavaScript, HTML (não que isso seja uma linguagem de programação), entre outras.

Além de apresentar uma interface fácil para a execução de programas, apesar de seu editor não ter nada de especial como as funcionalidas do Emacs, ele permite o gerenciamento de projetos que ficam salvos online.

Isso significa que você pode manter uma coleção de aplicativos no site deles, e além disso, contribuir na comunidade com algumas implementações (Alguém disposto a implementar uma árvore rubro-negra em Basic?) .

Com certeza o CodeIDE é muito interessante, principalmente para pessoas que precisam fazer programas curtos em vários micros diferentes, como estudantes ou participantes de maratonas de computação.

Só é uma pena que Lisp ainda não esteja disponível.

[Via WebTuga]

Posts Relacionados:

Acompanhe-nos por RSS, por Email ou via Twitter.
Veja como ter um desconto no Dreamhost: um excelente servidor web.

Provavelmente você ja deve ter ouvido falar de FILO, first in last out (primeiro a entrar é o ultimo a sair). Muitas (talvez todas) linguagens de programação usam uma estrutura FILO para controlar chamadas de funções e alocações de variáveis. Uma estrutura FILO também é chamada de pilha.

Uma pilha basicamente é um vetor e um controle de onde está o topo dessa pilha. No caso da pilha de uma linguagem de programação, como são os parâmetros e as variáveis de funções em execução ou em espera pelo término de uma outra função chamada por ela. Variáveis globais e/ou estáticas também são armazenadas na pilha. Quando uma função é chamada (ou um bloco é aberto), o marcador do topo da pilha é deslocado X bytes para frente, sendo X o espaço para alocar variáveis e/ou parâmetros. Quando a função (ou o bloco) termina, o marcador é deslocado novamente X bytes para trás, liberando o espaço para uma posterior alocação.

Em C, a pilha tem em torno de 8Mb. Isso é muita memória. Então chamadas de funções (a não ser um loop recursivo infinito) dificilmente irão exceder esse limite. Caso exceda, uma Segmentation Fault é lançada.

Apenas para complementar o post sobre VarArgs, agora que você conhece o funcionamento geral do sistema de controle de variáveis e parâmetros, é fácil notar que pelo menos parte da va_list lida com um ponteiro associado à pilha (por isso é necessário um parâmetro fixo, pois não é possível obter o endereço do local onde estão os parâmetros na pilha). Além disso a va_list deve cuidar de parâmetros passados por registradores.

Mais informações: Introduction To Algorithms, de Cormem, Leiserson, Rivest e Stein (CLRS) ou pilha -> Google

Próxima sexta: Recursão

Posts Relacionados:

Acompanhe-nos por RSS, por Email ou via Twitter.
Veja como ter um desconto no Dreamhost: um excelente servidor web.

Um dos maiores problemas que um programador encontra é a fase de testes do software. Praticamente sempre algum bug (erro) sintático, conceitual ou lógico está no meio do código muito bem disfarçado. Em C esse problema é ainda maior porque após a compilação do código, C gera pouquissímos erros e assim fica realmente complicado descobrir o que está acontecendo. Um simples ‘*’ pode tomar algumas horas do programador antes de ser corrigido. Essas horas perdidas significam que o projeto pode estar ficando atrasado, o que não é bom independente se o projeto é de software proprietário ou livre. Aqui vão algumas dicas para lidar com esses erros:

1. A melhor forma de lidar com erros é evitá-los. Planeje bastante o programa que você vai desenvolver (mesmo que seja pequeno). Estruture bem as funções que você vai usar. Minimize o tamanho das funções. É muito importante evitar funções que fazem muitas coisas de uma vez. Mantenha o código claro durante a programação. Esse tempo extra gasto costuma reduzir muito o tempo de depuração. Na verdade ele não é tempo gasto. É tempo investido.

2. Evite escrever grandes quantidades de código antes de depurar o código que forma a base para este novo.

3. Sempre comece a depurar a partir das funções mais simples e gradualmente começando a depurar funções mais complexas. Assim você garante a segurança das funções mais simples, que geralmente são usadas nas mais compplexas.

4. Faça bons casos de teste. Na maioria das vezes testes automatizados podem nos mostrar erros que nem imagináva-mos que poderiam ocorrer.

5. Para remover bugs encontrados, existem algumas estratégias como:
- Impressão de variáveis para que seja possível rastrear a execução do programa ou
- Usar um depurador (debugger)
O primeiro possui uma curva de aprendizado de 30 segundos. Basta saber usar o printf que já é possível depurar o seu código. Para usar o segundo, você terá que investir um certo tempo no aprendizado, mas novamente, é um bom investimento. É muito mais rápido e eficaz usar um depurador (como o gdb) do que tentar rastrear o código (as vezes, rastrear é impraticavel pois o sistema ou módulo é grande demais).

6. Lembre-se que qualquer código está sujeito a erros. É provado que é impossível provar que o seu código produzirá o resultado certo para qualquer entrada a que ele seja submetido. Um algoritmo pode ser provado correto, mas uma implementação nunca. Assim, bons casos de testes garantem, pelo menos, uma segurança satisfatória.

Mais informações: gdb -> Google

Na próxima semana: Pilha do C.

Posts Relacionados:

Acompanhe-nos por RSS, por Email ou via Twitter.
Veja como ter um desconto no Dreamhost: um excelente servidor web.