Recursividade

Recursividade

1. É uma técnica empregada na construção de algoritmos.

   • Melhorar a clareza e simplicidade.
   • Em alguns casos a solução não-recursiva é bem mais extensa e menos elegante.

2. Consiste em reduzirmos um determinado problema a uma instância menor, do mesmo problema.

   • Se o problema for pequeno, então resolva-o diretamente
   • Se o problema for grande:
     • Reduza o seu tamanho, criando uma instância menor do mesmo problema
     • Resolva a instância menor, aplicando o mesmo método
     • E finalmente, retorne ao problema original

3. A recursividade é uma estratégia que pode ser utilizada sempre que o cálculo de uma função para o valor n, pode ser descrita a partir do cálculo desta mesma função para o termo anterior (n-1).

4. Exemplos

   • Números naturais
   • Função fatorial
   • Árvore

5. Definição:

   • Dentro do corpo de uma função, chamar novamente a própria função. Define conjuntos infinitos com comandos finitos (conceito poderoso)
     • recursão DIRETA: a função A chama a própria função A
     • recursão INDIRETA: a função A chama uma função B que, por sua vez, chama A

6. Vantagens

   • A utilização de uma função recursiva pode simplificar a solução de alguns problemas;
   • Pode-se obter um código mais conciso e eficaz nessas situações;
   • Uma solução recursiva pode, por outro lado, eliminar a necessidade de manter o controle manual sobre uma série de variáveis normalmente associadas aos métodos alternativos à recursividade.

7. Desvantagens

   • As funções recursivas são geralmente mais lentas e ocupam mais memória do que as funções iterativas equivalentes, uma vez que são feitas muitas chamadas consecutivas a funções;
   • Um erro de implementação pode levar ao esgotamento dos recursos associados à pilha que gere a chamada a funções. Isto é, caso não seja indicada nenhuma condição de paragem (F(x) > 0 onde x é decrescente), ou essa condição foi definida de forma errada e nunca será satisfeita, então o processo recursivo não terá fim.

8. Execução

   • Internamente, quando qualquer chamada de função é feita dentro de um programa, é criado um Registro de Ativação na Pilha de Execução do programa
   • O registro de ativação armazena os parâmetros e variáveis locais da função bem como o “ponto de retorno” no programa ou subprograma que chamou essa função.
   • Ao final da execução dessa função, o registro é desempilhado e a execução volta ao subprograma que chamou a função

9. A recursividade nem sempre é a melhor solução, mesmo quando a definição matemática do problema é feita em termos recursivos.

10. Recursividade vale a pena para Algoritmos complexos, cuja a implementação iterativa é complexa e normalmente requer o uso explícito de uma pilha:

    • Dividir para Conquistar (Ex. Quicksort)
      • Duas chamadas recursivas
        • Cada uma resolvendo a metade do problema
      • Muito usado na prática
        • Solução eficiente de problemas / Decomposição
      • Não se reduz trivialmente como fatorial
        • Duas chamadas recursivas
      • Não produz recomputação excessiva como fibonacci
        • Porções diferentes do problema
    • Caminhamento em Árvores (pesquisa, backtracking)

Images and files in the map