Projete em pseudocódigo um algoritmo recursivo map_recursive(L,f) que recebe uma lista L e uma função f e…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Construir e simular algoritmos, de forma independente ou em colaboração, que resolvam problemas simples e do cotidiano com uso de sequências, seleções condicionais e repetições de instruções.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Projete em pseudocódigo um algoritmo recursivo map_recursive(L,f) que recebe uma lista L e uma função f e retorna uma nova lista aplicando f a cada elemento, sem modificar L. Explique a complexidade temporal e o uso de memória.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
Exemplo de solução: funcao map_recursive(L,f): se L == [] entao retorne [] senao head := L[0] tail := L[1:] return concatenar([ f(head) ], map_recursive(tail,f)) Correção e complexidade: a função cria uma nova lista com n elementos; tempo O(n) (uma aplicação de f por elemento) e memória adicional O(n) pela nova lista e O(n) de profundidade de pilha. Alternativa de cauda: usar acumulador e inverter no final para reduzir custos de concatenação em algumas implementações.
Explicação
O algoritmo utiliza recursão para percorrer a lista, aplicando a função a cada elemento e construindo uma nova lista. A complexidade temporal é O(n) devido à necessidade de aplicar a função a cada elemento da lista, enquanto a complexidade de memória é O(n) por causa da nova lista e da profundidade da pilha de chamadas recursivas. A sugestão de usar um acumulador e inverter a lista no final visa otimizar a operação de concatenação, que pode ser custosa em algumas implementações.
Raio-X da questão
algoritmo recursivo
avaliacao
funções recursivas · estruturas de dados
Revisar conceitos de recursão e complexidade de algoritmos.
O aluno pode confundir a implementação de uma função recursiva com uma função iterativa, resultando em um código que não respeita a recursão.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Os aplicativos de mapa, como o GPS, ajudam o carro de entregas a chegar à casa do cliente. O aplicativo compara dois…
- Lia organiza carrinhos, bonecas e blocos separando cada tipo, colocando-os em caixas e guardando as caixas na…
- Em um jogo, uma personagem controlada por IA precisa chegar a um tesouro sem bater nas paredes. Qual instrução ajuda a…
- Desenhe um algoritmo em pseudocódigo que, dada uma matriz M[N][M] com 0 (livre) e 1 (bloqueado), identifique todas as…
- Em um programa, Substring(codigo, início, quantidade) pega letras do texto a partir da posição indicada, e…
- Projete um algoritmo em pseudocódigo que, dadas as variáveis temperatura (inteiro ºC), ocupacao (inteiro, número de…
🔎 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