Considere um algoritmo recursivo que percorre uma lista L de n elementos, fazendo uma chamada recursiva por…
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
Considere um algoritmo recursivo que percorre uma lista L de n elementos, fazendo uma chamada recursiva por elemento e sem usar acumulador: qual é a complexidade de espaço adicional em função de n (considere a pilha de chamadas)?
- A) Complexidade de espaço O(log n) para n elementos.
- B) Complexidade de espaço O(1) para n elementos.
- C) Complexidade de espaço O(n^2) devido à pilha de chamadas.
- D) Complexidade de espaço constante, não dependente de n.
- E) Complexidade de espaço O(n) devido à pilha de chamadas recursivas.
✅ Resposta correta: alternativa E
Resolução passo a passo
- Identifique o que o enunciado descreve. O algoritmo percorre uma lista de n elementos e faz uma chamada recursiva para cada elemento, sem acumulador. Assim, cada chamada espera o retorno da seguinte, e as chamadas ficam empilhadas na pilha de execução.
- Calcule a profundidade máxima da pilha. Como há uma chamada por elemento, quando o algoritmo está no último elemento existem cerca de n chamadas ativas ao mesmo tempo, cada uma com seu próprio registro (variáveis locais, endereço de retorno e parâmetros).
- Some o espaço. Cada registro ocupa uma quantidade limitada de memória que não cresce com n, então o espaço total da pilha é proporcional a n, ou seja, O(n). Pelo enunciado, o espaço adicional é esse, sem contar a própria lista de entrada.
- Compare com as alternativas. A alternativa A está errada porque O(log n) corresponde a algoritmos que dividem o problema pela metade a cada chamada, como a busca binária, e aqui o problema diminui apenas um elemento por vez. A alternativa B está errada porque O(1) exigiria um número fixo de chamadas, o que não ocorre quando há uma chamada por elemento. A alternativa C está errada porque O(n^2) não surge de uma pilha com uma chamada por elemento, pois a profundidade cresce linearmente. A alternativa D está errada porque afirma espaço constante, o que contradiz a profundidade crescente da pilha.
- Conclusão. A alternativa correta é a E, complexidade de espaço O(n) devido à pilha de chamadas recursivas, coincidindo com o gabarito oficial.
💡 Dica: Analise a estrutura do algoritmo recursivo e a pilha de chamadas.
Alternativa por alternativa
O aluno provavelmente associou recursão a algoritmos de divisão e conquista, como a busca binária, que têm profundidade logarítmica. Não percebeu que aqui o problema diminui apenas um elemento por chamada.
Por que engana: Confundir a complexidade de espaço com a complexidade de tempo, avaliando incorretamente a pilha de chamadas.
O aluno pode ter imaginado que, como não há acumulador nem estruturas auxiliares, o espaço seria constante. Ignorou que cada chamada recursiva ocupa um registro na pilha e que essas chamadas se acumulam.
O aluno pode ter confundido a profundidade da pilha com o número de comparações ou pares de elementos, que em alguns algoritmos cresce quadraticamente. A pilha, porém, cresce linearmente com o número de chamadas.
O aluno provavelmente pensou que, por não haver variáveis que armazenem os n elementos, o espaço não depende de n. Não considerou que a pilha de chamadas cresce a cada elemento processado.
Cada chamada empilha um quadro; para n elementos haverá até n quadros simultâneos, gerando espaço linear.
Raio-X da questão
complexidade de espaço
avaliacao
algoritmos recursivos · complexidade de algoritmos
Revisar conceitos de algoritmos recursivos e complexidade de espaço.
Confundir a complexidade de espaço com a complexidade de tempo, avaliando incorretamente a pilha de chamadas.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Em pseudocódigo, ao implementar um algoritmo recursivo que percorre uma lista L processando exatamente um elemento por…
- Em pseudocódigo, qual deve ser o caso base de um algoritmo recursivo que conta elementos de uma lista L (variável L)…
- Em uma atividade de análise de algoritmos, uma turma usa a função recursiva count_occurrences(L, x) para contar quantas…
- Projete em pseudocódigo uma função recursiva permutar(L) que recebe uma lista L com n elementos distintos e retorna uma…
- Projete em pseudocódigo uma função recursiva maximo(L) que recebe uma lista não vazia de inteiros e retorna o maior…
- 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