MyLeoNes™

Recursão — Informática, 14–17 anos

Como um problema pode ser resolvido criando uma versão mais pequena do mesmo problema, com um ponto claro onde o processo termina.

Ideia

Recursão acontece quando uma função resolve uma tarefa chamando-se a si própria com uma entrada mais pequena ou simples. Também precisa de um caso-base: uma situação suficientemente simples para ser respondida diretamente. Cada chamada aproxima-se desse caso, como abrir uma caixa mais pequena dentro de outra até chegar à última.

Porque é importante

Alguns problemas contêm cópias mais pequenas de si próprios. As pastas contêm pastas, as árvores genealógicas contêm ramos e um labirinto pode conter secções mais pequenas para explorar. A recursão descreve naturalmente estas formas, porque as mesmas instruções podem ser reutilizadas em vez de escrever código para cada profundidade possível.

Exemplo resolvido

Para calcular 4 fatorial, define-se fact(1)=1 como caso-base. Depois, fact(4)=4×fact(3), fact(3)=3×fact(2) e fact(2)=2×fact(1). Substituindo de baixo para cima, obtemos 2×1=2, 3×2=6 e 4×6=24; portanto, 4!=24.

Armadilha comum

Um erro compreensível é escrever primeiro a chamada da própria função e esquecer o caso-base ou o passo que conduz até ele. Nesse caso, o código continua a chamar-se sem fim, porque o computador não adivinha quando a tarefa terminou. Mesmo com um caso-base, um passo errado pode fazer a entrada crescer em vez de diminuir.

Onde aparece

Os navegadores, as ferramentas de ficheiros e os sistemas de pesquisa exploram muitas vezes pastas aninhadas ou páginas ligadas usando ideias recursivas. O software de imagem também pode processar uma imagem dividindo-a em regiões menores e voltando a dividi-las. A recursão é útil porque a mesma ação se aplica a cada nível até uma região ser suficientemente pequena.

Continua a explorar

Outras línguas

A carregar o MyLeoNes™…