Questão de Algoritmos e Estrutura de Dados — Algoritmos — IDCAP 2023

Recursividade

Gabarito: letra B. A frase "decompondo-os repetidamente em subproblemas do mesmo tipo" descreve exatamente a recursão, um paradigma onde uma função invoca a si mesma em instâncias menores do problema. A Torre de Hanói é o exemplo clássico de algoritmo recursivo, resolvido por chamadas recursivas até o caso base.

Alternativa A — ❌ Incorreta

Programação dinâmica também divide em subproblemas, mas tem como diferencial o armazenamento de soluções de subproblemas para evitar recálculo (memoização). A descrição do enunciado não menciona reutilização de resultados, apenas a decomposição repetida em subproblemas do mesmo tipo, o que é próprio da recursão.

Alternativa B — ✅ Correta ⟵ GABARITO

A recursão é a técnica em que um problema é resolvido por meio de chamadas a si mesmo com entradas menores, até atingir um caso base. A Torre de Hanói é resolvida de forma natural com recursão: move-se n-1 discos, move-se o maior, e move-se novamente n-1 discos. Isso corresponde perfeitamente à definição do enunciado.

Alternativa C — ❌ Incorreta

Backtracking é uma estratégia de busca que explora candidatos e retrocede quando não encontra solução. Embora possa usar recursão, não é definido pela simples decomposição repetida em subproblemas do mesmo tipo; seu foco é a tentativa e erro sistemática.

Alternativa D — ❌ Incorreta

Força bruta testa todas as possibilidades exaustivamente até encontrar a solução, sem necessariamente decompor o problema em subproblemas menores.

Alternativa E — ❌ Incorreta

Divisão e conquista também divide o problema em subproblemas, mas geralmente combina as soluções ao final. A Torre de Hanói é um exemplo de recursão, não de divisão e conquista (embora todo algoritmo de divisão e conquista seja recursivo, o inverso não é verdade). O enunciado enfatiza "subproblemas do mesmo tipo" e cita a Torre de Hanói, que é uma aplicação recursiva pura.

Gabarito: letra B.