Projete em pseudocódigo uma função recursiva maximo(L) que recebe uma lista não vazia de inteiros e retorna o…

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

Questões parecidas com resolução

• Em uma usina, cada estado de uma turbina é registrado com um código de dois bits: | Estado | Código | |---|---| | Parada…
• No controle de um satélite, um gráfico de barras descrito pela equipe registra: com o sistema operacional iniciado, o…
• O clube de jogos da escola vai usar um programa simples para registrar cada participante. Em cada cadastro, a pessoa…
• Na horta da escola, uma estação simples registra a temperatura informada por um sensor. O programa deve mostrar essa…
• Pesquisadores acompanham o funcionamento de um robô que cuida de seis placas solares em uma estação de pesquisa. O robô…
• Por que alguns tablets de um centro cultural aparecem como disponíveis, embora estejam guardados para conserto? Para…

Todas as questões de Programação - Linguagem de programação