4.3. Calculando a Soma de Uma Lista de Números¶

Nós vamos iniciar nossa investigação com um problema simples que você já sabe resolver sem usar recursão. Imagine que você queira calcular a soma de uma lista de números tal como: $[1, 3, 5, 7, 9]$. Uma função iterativa que calcula a soma é mostrada no ActiveCode 1. A função usa uma variável acumuladora (“soma”) que calcula a somatória de todos os números da lista começando com $0$ e adicionando cada número da lista.

def somalista(numeros):

    soma = 0

    for i in numeros:

        soma = soma + i

    return soma

​

print(somalista([1,3,5,7,9]))

​

Imagine por um minuto que você não tem os comandos de repetição while e for. Como você calcularia a soma de uma lista de números? Se você fosse um matemático, você poderia começar lembrando que a adição é uma função definida par dois parâmetros, um par de números. Para redefinir o problema de adição de lista para adição de um par de números, podemos reescrever a lista como uma expressão com parênteses. Essa expressão poderia ser como essa:

Nós podemos também formar uma expressão com parênteses em ordem contrária:

Observe que o conjunto mais interno de parênteses, $(7 + 9)$, é um problema que podemos resolver sem comandos de repetição ou qualquer construção especial. De fato, podemos usar a seguinte sequência de simplificações para calcular a soma final.

Como podemos considerar essa ideia e aplicá-la em um programa em Python? Primeiro vamos considerar o problema de soma em termos de listas em Python. Podemos dizer que a soma da lista numeros é a soma do primeiro elemento da lista (numeros[0]), e a soma dos números do resto da lista (numeros[1:]). Para escrever isso em forma funcional:

Nessa equação $primeiro(numeros)$ retorna o primeiro elemento da lista $resto(numeros)$ e retorna a lista menos o primeiro elemento. Isso é facilmente expresso em Python como mostrado no ActiveCode 2.

def somalista(numeros):

   if len(numeros) == 1:

        return numeros[0]

   else:

        return numeros[0] + somalista(numeros[1:])

​

print(somalista([1,3,5,7,9]))

​

Há algumas ideias básicas que devem ser observadas nesse código. Primeiro, na linha 2 nós verificamos se a lista possui apenas um elemento. Essa verificação é crucial e é a forma de sair da função. A soma de uma lista de comprimento 1 é trivial; é simplesmente o número que está na lista. Segundo, na linha 5, nossa função chama a si mesma! Essa é a razão pela qual chamamos o algoritmo sum de recursivo. Uma função recursiva é uma função que chama a si mesma.

A figura 1 mostra a série de chamadas recursivas necessárias para somar a lista $[1, 3, 5, 7, 9]$. Você deve considerar essa série de chamadas como um série de simplificações. Cada vez que fazemos uma chamada recursiva estamos resolvendo um problema menor, até chegar a um ponto onde o problema não precisa mais ficar menor.

Figura 1: Série de chamadas recursivas para somar (sum) uma lista de números¶

Quando chegamos ao ponto onde o problema se torna tão simples quanto possível, passamos a montar as soluções de cada um dos problemas menores até resolver o problema inicial. A figura 2 mostra as adições realizadas a medida que sum vai retornando pela série de chamadas. Quando sum retorna da primeira chamada, nós obtemos a solução de todo o problema.

Figura 2: Série de returns das chamadas recursivas para somar (sum) uma lista de números¶