Ao projetar um algoritmo recursivo que recalcula repetidamente os mesmos subproblemas, qual técnica baseada em…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Construir soluções de problemas usando a técnica de recursão e automatizar tais soluções usando uma linguagem de programação.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Ao projetar um algoritmo recursivo que recalcula repetidamente os mesmos subproblemas, qual técnica baseada em armazenar resultados anteriores reduz o tempo de execução?
- A) Repetição de chamadas sem modificar argumentos.
- B) Divisão de problemas em partes menores, sem armazenar resultados.
- C) Usar apenas recursão simples e esperar por resultados.
- D) Memoização: armazenar resultados em uma tabela (cache) e reutilizá-los
- E) Implementação de loops aninhados em vez de recursão.
✅ Resposta correta: alternativa D
Resolução passo a passo
- O enunciado descreve um algoritmo recursivo que recalcula os mesmos subproblemas várias vezes, ou seja, há sobreposição de subproblemas e trabalho desperdiçado.
- A técnica que resolve esse desperdício é guardar o resultado de cada subproblema já calculado (em uma tabela ou cache) e, quando ele aparecer de novo, reutilizar o valor armazenado em vez de recalculá-lo. Esse procedimento chama-se memoização.
- Logo, a alternativa D está correta, pois descreve exatamente armazenar resultados em uma tabela (cache) e reutilizá-los.
- A alternativa A está errada, pois repetir chamadas sem modificar argumentos apenas repete o mesmo trabalho e não reduz o tempo.
- A alternativa B está errada, pois dividir o problema em partes menores é a própria essência da recursão, mas sem armazenar resultados o recálculo continua ocorrendo.
- A alternativa C está errada, pois a recursão simples é justamente o que causa o recálculo; esperar pelos resultados não os reaproveita.
- A alternativa E está errada, pois trocar recursão por loops aninhados não é a técnica que armazena resultados e não garante redução do tempo em geral.
- Conclusão: o gabarito oficial D está correto.
💡 Dica: Pense na técnica que armazena resultados de subproblemas.
Alternativa por alternativa
O aluno acredita que repetir chamadas idênticas já resolve o problema, sem perceber que as mesmas entradas geram o mesmo cálculo de novo.
O aluno confunde a estratégia de dividir o problema (dividir e conquistar) com a otimização pedida, que exige guardar os resultados já obtidos.
Por que engana: O aluno pode confundir a técnica de memoização com a simples repetição de chamadas, não percebendo a importância de armazenar resultados para otimizar o tempo de execução.
O aluno supõe que a recursão simples, por si só, é a solução eficiente, sem notar que ela é justamente a origem do recálculo de subproblemas.
Memoização evita recomputação gravando resultados de subproblemas em uma tabela (por exemplo, mapa/array), transformando muitas recursões exponenciais em custo polinomial.
O aluno associa eficiência apenas à troca de recursão por iteração, sem perceber que o ganho vem do armazenamento dos resultados, não da estrutura de repetição.
Raio-X da questão
algoritmo recursivo
avaliacao
algoritmos recursivos · memoização
Revisar técnicas de otimização em algoritmos recursivos.
O aluno pode confundir a técnica de memoização com a simples repetição de chamadas, não percebendo a importância de armazenar resultados para otimizar o tempo de execução.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Ao generalizar um algoritmo recursivo que calcula custo mínimo em uma rede (grafo) para múltiplas instâncias, qual…
- Em um projeto de programação, uma equipe precisa calcular o termo de número n da sequência de Fibonacci usando recursão…
- Qual técnica pode ser utilizada para resolver problemas onde a mesma solução pode ser aplicada repetidamente, como…
- Uma equipe desenvolve uma central meteorológica para regiões remotas. O microcontrolador do equipamento possui apenas 1…
- Qual técnica de programação pode ser utilizada para resolver um problema em que uma função chama a si mesma?
- Analise a função recursiva que calcula o fatorial de um número. Qual é a estrutura de dados mais adequada para armazenar…
Todas as questões de Programação - Programação com listas e recursão
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog