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.

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.

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¶