Leia o trecho abaixo de um algoritmo recursivo que soma elementos de uma lista: fun soma(L): se L == [] então…

Questão

Leia o trecho abaixo de um algoritmo recursivo que soma elementos de uma lista: fun soma(L): se L == [] então retorne 0 senão retorne L[0] + soma(L[1:]) Avalie dois problemas que podem surgir ao aplicar essa recursão em listas muito longas e proponha um algoritmo iterativo que evite a recursão.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Problemas: (1) Empilhamento de chamadas recursivas pode causar estouro de pilha (stack overflow) em listas muito longas, interrompendo o programa. (2) O uso de slicing L[1:] em cada chamada pode criar cópias da lista, aumentando consumo de memória e tempo (possível comportamento O(n^2)). Proposta iterativa (modelo): fun soma_iterativa(L): total = 0 para cada elemento x em L: total = total + x retorne total Essa versão percorre a lista uma vez, usa espaço O(1) adicional e evita aumento da pilha; em linguagens onde for-in não existe, usar índice i de 0 até len(L)-1 e somar L[i].

Explicação

A resposta identifica problemas práticos da recursão, como o estouro de pilha e o aumento do consumo de memória devido ao uso de slicing. A proposta do algoritmo iterativo resolve essas questões ao realizar a soma em uma única passagem pela lista, utilizando espaço constante. Isso torna o algoritmo mais eficiente em termos de tempo e memória, sendo adequado para listas longas.

Raio-X da questão

Questões parecidas com resolução

• Considere a função recursiva em pseudocódigo: função soma(L): se L == [] retorne 0; senão retorne L[0] + soma(L[1:])…

Todas as questões de Leitura e interpretação de tabelas e gráficos (de colunas ou barras simples ou múltiplas) referentes a variáveis categóricas e variáveis numéricas