Em pseudocódigo, ao implementar um algoritmo recursivo que percorre uma lista L processando exatamente um…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Aplicar a estratégia de decomposição para resolver problemas complexos, dividindo esse problema em partes menores, resolvendo-as e combinando suas soluções.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Em pseudocódigo, ao implementar um algoritmo recursivo que percorre uma lista L processando exatamente um elemento por chamada, qual é a ordem de crescimento da profundidade máxima da pilha de chamadas em função do tamanho n de L?
- A) A profundidade máxima nunca ultrapassa O(1) para listas de qualquer tamanho.
- B) A profundidade da pilha de chamadas é invariável e não depende do tamanho da lista.
- C) A profundidade da pilha de chamadas cresce exponencialmente: O(2^n).
- D) A profundidade máxima da pilha de chamadas cresce em quadrado: O(n²).
- E) A profundidade cresce linearmente em relação a n: O(n).
✅ Resposta correta: alternativa E
Resolução passo a passo
- Analise o funcionamento da recursão. Cada chamada processa exatamente um elemento da lista e, em seguida, chama a si mesma para tratar o restante, até que a lista esteja vazia (caso base).
- Conte quantas chamadas ficam ativas ao mesmo tempo no ponto de maior profundidade. Como cada chamada espera o retorno da próxima antes de terminar, para uma lista de n elementos são feitas n chamadas aninhadas mais o caso base, todas empilhadas na pilha de chamadas.
- Conclua a ordem de crescimento. A profundidade máxima cresce proporcionalmente a n, ou seja, O(n), porque cada elemento adiciona um quadro à pilha.
- Verifique as alternativas erradas. A alternativa A está errada porque a profundidade depende de n e não se limita a O(1). A alternativa B está errada porque a profundidade cresce com o tamanho da lista, não sendo invariável. A alternativa C está errada porque o crescimento é linear, e não exponencial, já que cada chamada gera apenas uma nova chamada. A alternativa D está errada porque não há aninhamento quadrático: cada chamada abre apenas um nível novo.
- Conclusão. O gabarito E está correto, pois a profundidade máxima da pilha de chamadas é O(n).
💡 Dica: Considere a relação entre o tamanho da lista e a profundidade da recursão.
Alternativa por alternativa
Imagina que, como cada chamada trata só um elemento, a pilha não acumula quadros e permanece de tamanho constante.
Acredita que, por a recursão ser sempre igual, a pilha tem tamanho fixo independentemente de quantos elementos a lista possui.
Confunde o número total de chamadas ou combinações com a profundidade, supondo que cada chamada dobra o número de níveis ativos.
Por que engana: Confundir a profundidade da pilha de chamadas com a complexidade do algoritmo, pensando que é constante para qualquer tamanho de lista.
Supõe que cada elemento gera um laço interno sobre os demais, produzindo aninhamento quadrático, quando na recursão simples há apenas um nível novo por elemento.
Cada chamada recursiva processa um elemento e empilha uma nova ativação; assim, para n elementos há proporcionalmente n chamadas simultâneas no pior caso.
Raio-X da questão
algoritmo recursivo
avaliacao
algoritmo recursivo · complexidade de algoritmos
Revisar conceitos de recursão e pilha de chamadas.
Confundir a profundidade da pilha de chamadas com a complexidade do algoritmo, pensando que é constante para qualquer tamanho de lista.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Considere um algoritmo recursivo que percorre uma lista L de n elementos, fazendo uma chamada recursiva por elemento e…
- Projete em pseudocódigo uma função recursiva profundidade(L) que recebe uma lista L que pode conter elementos e…
- Em pseudocódigo, qual deve ser o caso base de um algoritmo recursivo que conta elementos de uma lista L (variável L)…
- Projete em pseudocódigo uma função recursiva maximo(L) que recebe uma lista não vazia de inteiros e retorna o maior…
- Projete em pseudocódigo uma função recursiva permutar(L) que recebe uma lista L com n elementos distintos e retorna uma…
- Projete uma função recursiva em pseudocódigo flatten(L) que recebe uma lista L que pode conter inteiros e sublistas…
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