Projete em pseudocódigo uma função recursiva maximo(L) que recebe uma lista não vazia de inteiros e retorna o…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Elaborar algoritmos que envolvam instruções sequenciais, de repetição e de seleção usando uma linguagem de programação.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Projete em pseudocódigo uma função recursiva maximo(L) que recebe uma lista não vazia de inteiros e retorna o maior valor. Descreva como a recursão divide o problema e analise a complexidade temporal e a profundidade da pilha de chamadas.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
Exemplo de solução: fun maximo(L): se comprimento(L) == 1 então retorne primeiro(L) senão: m = maximo(resto(L)) se primeiro(L) > m então retorne primeiro(L) senão retorne m Divisão: cada chamada reduz a lista removendo a cabeça, o subproblema tem tamanho n-1. Complexidade temporal: O(n) porque cada elemento é comparado uma vez. Profundidade da pilha: O(n) em implementação recursiva simples (uma chamada por elemento). Alternativa: versão com acumulador (tail recursion) ou iteração reduz a profundidade da pilha para O(1).
Explicação
A solução apresentada utiliza recursão para comparar elementos da lista, reduzindo o problema a cada chamada até chegar ao caso base, que é uma lista com um único elemento. A complexidade temporal é linear, pois cada elemento é acessado uma vez, enquanto a profundidade da pilha de chamadas reflete o número de elementos, resultando em uma profundidade máxima igual ao tamanho da lista. Alternativas como a recursão de cauda ou iteração podem otimizar o uso da pilha, evitando o crescimento excessivo em casos de listas muito longas.
Raio-X da questão
função recursiva
avaliacao
funções recursivas · listas e arrays
Revisar conceitos de recursão e análise de complexidade.
O aluno pode confundir a lógica de recursão, tentando resolver o problema de forma iterativa em vez de recursiva.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Projete em pseudocódigo um algoritmo recursivo max_recursive(L) que recebe uma lista não vazia L de inteiros e retorna o…
- Projete em pseudocódigo uma função recursiva profundidade(L) que recebe uma lista L que pode conter elementos e…
- Projete em pseudocódigo uma função recursiva que verifica se uma lista de inteiros L está estritamente crescente (cada…
- Projete em pseudocódigo uma função recursiva subsequencias(L) que recebe uma lista L de inteiros e retorna a lista de…
- Projete uma função recursiva em pseudocódigo flatten(L) que recebe uma lista L que pode conter inteiros e sublistas…
- Projete em pseudocódigo uma função recursiva quicksort(L) que ordena uma lista L de inteiros em ordem não crescente…
🔎 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