Recursão: resolver um problema com versões mais pequenas de si próprio — Tecnologia, 14–17 anos
A recursão permite a um programa repetir uma ideia chamando a si próprio para um caso mais pequeno. Também tem de saber quando parar, ou o processo nunca termina.
Uma cópia mais pequena do mesmo problema
Imagina abrir caixas encaixadas: dentro de cada uma há outra mais pequena, até chegar à última, que está vazia. Um programa recursivo faz algo semelhante, resolvendo uma versão mais pequena da tarefa. Precisa de um caso-base com resposta directa.
Por que usar a recursão?
Alguns problemas já têm uma forma ramificada ou encaixada: as pastas contêm pastas, as páginas ligam a outras páginas e as árvores genealógicas separam-se em ramos. A recursão acompanha essa forma, tornando o código mais claro do que uma longa lista de casos especiais.
Exemplo resolvido: factorial
Para calcular 4!, define 1! como 1 e use n! = n × (n−1)!. Assim, 4! passa a 4 × 3!, depois 4 × 3 × 2!, e depois 4 × 3 × 2 × 1!, o que dá 24. O caso-base 1! pára a cadeia.
O ponto de paragem em falta
Um erro comum é escrever a chamada a si próprio e esquecer o caso-base, ou alterar tão pouco o valor que ele nunca lá chega. É um erro compreensível, porque o passo repetido parece ser a ideia principal. O resultado costuma ser um stack overflow: chamadas inacabadas a mais.
Onde aparece
Os exploradores de ficheiros podem procurar em pastas dentro de pastas, e os programas de desenho podem criar formas ramificadas, como árvores ou flocos de neve. Estas tarefas têm uma estrutura encaixada, por isso a recursão descreve-as naturalmente. Nem sempre é a mais rápida; um método iterativo pode usar menos memória.
Continua a explorar
Outras línguas
A carregar o MyLeoNes™…