Você consegue escrever 3 soluções distintas para calcular a soma de uma lista de números?

A maioria das linguagens modernas já possuem uma função pronta para iterar sobre os elementos de uma coleção de dados e retornar sua soma. De forma alguma sugiro que você escreva sua própria solução para este tipo de problema, visto que o objetivo aqui é puramente didático.

Problema:

Escreva 3 funções que calculem a soma de uma lista utilizando um loop com for, um loop com while e recursividade.

Entrada:

  • Uma lista L de n inteiros, onde:  -100 <= L[i] >= 100 e  0 <= n >=100.
  • Todos os itens são inteiros válidos. Não é necessário sanitizar os dados de entrada.

Saída:

  • A soma dos itens de L[0] a L[n-1]

Antes de ler o resto, sugiro que você pare um pouco e tente formular suas próprias soluções, mesmo que em pseudocódigo.


Casos de testes e exemplos:

O formato usado para descrição é de: ƒ(Entrada) -> Saída.

Retorna a soma de seus elementos

ƒ([10, 30, 25, 15, 40]) -> 120

A função deve diferenciar valores negativos e positivos

ƒ([-3, -2, -1, 1, 2, 3]) -> 0

Uma lista vazia deve retornar soma 0

ƒ([]) -> 0

Uma lista cujos valores são zero, retorna soma 0

ƒ([0, 0, 0]) -> 0

Uma lista com um único elemento, deve retornar este único valor

ƒ([5]) -> 5

Uma lista de tamanho máximo (len(Entrada) == 100) retorna sua soma sem problema

ƒ(range(0, 100)) -> 4950

Para este problema em particular, já temos a função built-in sum, que sempre retornará o valor correto. Sendo assim, basta verificar que para cada um dos nossos casos de teste acima, o valor de saída seja igual ao de sum.

sum_of_numbers = sum(a_list)

assert for_loop_sum(a_list) == sum_of_numbers
assert while_loop_sum(a_list) == sum_of_numbers
assert recursion_sum(a_list) == sum_of_numbers

Obs.: Nos meus exemplos de código, com intuito de melhorar a legibilidade, utilizo a sintaxe presente em python >3.4 de type annotations/hint. Se você não tem familiaridade com essa sintaxe, ainda vou escrever um post e linkar aqui.

For Loop

É a solução mais fácil e óbvia de se pensar, com menor custo de memória. Utilizamos uma variável auxiliar list_sum, inicializada com valor 0 para armazenar os resultados das somas parciais.

def for_loop_sum(a_list: list) -> int:
    list_sum = 0
    for i in a_list:
        list_sum += i
    return list_sum

While Loop

Um pouco mais complexa do que a solução acima. Utiliza duas outras variáveis auxiliares: i para controle do índice atual dentro do laço e list_size, que corresponde a quantidade de elementos de a_list.

Obs.: Coleções de dados nativas em python (listas, dicionários, tuplas, sets, etc…) mantém a informação sobre o seu tamanho, não sendo necessário o calculo a cada vez que a função len() é chamada e tornando essa operação, O(1). O custo dessa linha pode diferir em outras linguagens.

def while_loop_sum(a_list: list) -> int:
    list_size = len(a_list)
    list_sum = 0
    i = 0

    while i < list_size:
        list_sum += a_list[i]
        i += 1

    return list_sum

Recursividade

Não utiliza nenhuma variável auxiliar, mas requer algum conhecimento de como funcionam funções recursivas (Se nunca viu isso, te recomendo dar uma lida nisso).

Para entender a solução, precisamos formular uma definição recursiva. Para soma de n itens de uma lista, temos que, a soma dos itens de uma lista é igual ao primeiro item da lista, mais a soma do resto dos itens. Ou seja: soma(lista) = lista[0] + soma(1 até n)

def recursion_sum(a_list: list) -> int:
    if not a_list:
        return 0

    return a_list[0] + recursion_sum(a_list[1:])

Temos como caso base(condição de parada), uma lista vazia (em python, not a_list == True para uma lista vazia. Esta é considerada uma verificação pythonica).

if not a_list:
    return 0

Como passo recursivo, chamados novamente a função, fornecendo um slice da lista original menos o primeiro índice.

return a_list[0] + recursion_sum(a_list[1:])

Vale lembrar que, apesar da fácil legibilidade, essa é uma péssima solução. Dois motivos são facilmente observáveis:

  1. O tamanho da pilha cresce de acordo com o tamanho de n (tamanho da lista), ou seja, tamanhos muito grandes, geram pilhas de recursão muito grandes, o que pode gerar um RecursionError.
  2. A cada chamada fazemos um slice da lista de entrada e essa operação possui um custo.

Conclusão

Esse foi o meu primeiro post de uma série de 5 problemas em dificuldade crescente. Espero trazer outros tópicos interessantes e ensinar algo ao longo do processo. Caso você tenha  alguma dúvida, correção, ou qualquer outra coisa a contribuir, deixe um comentário ou entre em contato diretamente comigo!

Anúncios

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s