Considere um algoritmo recursivo que percorre uma lista L de n elementos, fazendo uma chamada recursiva por…

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)?

1. A) Complexidade de espaço O(log n) para n elementos.
2. B) Complexidade de espaço O(1) para n elementos.
3. C) Complexidade de espaço O(n^2) devido à pilha de chamadas.
4. D) Complexidade de espaço constante, não dependente de n.
5. E) Complexidade de espaço O(n) devido à pilha de chamadas recursivas.

✅ Resposta correta: alternativa E

Resolução passo a passo

1. 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.
2. 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).
3. 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.
4. 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.
5. 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

Raio-X da questão

Questões parecidas com resolução

• Na aula, a turma mediu estas temperaturas: 20, 24, 21, 23 e 22 graus. Qual foi a média das temperaturas?
• Em uma estufa, um programa analisa a umidade de cinco canteiros, na ordem indicada, e aciona a irrigação quando a…
• Na feira cultural da escola, um grupo criou uma lista com as músicas que tocarão no palco: abertura, apresentação de…
• Na horta da escola, foram registradas as umidades do solo em uma lista: [42, 37, 35]. Uma função recursiva verifica se…
• Uma banca de feira registra em uma lista o preço de cada cesta vendida durante a manhã. Para calcular o total…
• Pesquisadores acompanham a qualidade da água em estações de um rio e precisam automatizar a leitura dos sensores. No…

Todas as questões de Programação - Programação com listas e recursão