Tema: Recursividade

Tema: Recursividade

1. Procedimento

   • Recursivo
     • procedimento contém, em sua descrição, uma ou mais chamadas a si mesmo.
   • Iterativo (não recursivo)
     • todas as chamadas são externas
   • Todo procedimento recursivo ou não, deve possuir pelo menos uma chamada externa.

2. Todo procedimento recursivo possui um correspondente iterativo (não recursivo) que executa a mesma computação

   • Os procedimentos recursivos são mais concisos (objetivos) que os não recursivos. É aparente a relação direta entre um procedimento recursivo e uma prova por indução matemática, o que torna mais fácil a verificação da correção.
     • Entretanto, os procedimentos recursivos podem perder desempenho, pois alocam muita memória e pilha, além de existir o crescimento exponencial de chamadas
       • Um procedimento recursivo precisa ter uma condição de parada, caso contrário será executado indefinidamente.
         • Apesar de todas essas vantagens, muitas vezes um procedimento não recursivo equivalente pode ser mais eficaz

3. Pode fazer uma chamada a si mesmo de forma direta (o algoritmo é chamado dentro do próprio) ou indireta (o algoritmo chama outro algoritmo que por sua vez possui uma chamada ao primeiro);

4. É a técnica que define um problema em termos de uma ou mais versões menores do mesmo problema. Pode ser usada sempre que for possível expressar a solução de um problema em função do próprio.

Images and files in the map