Recursão

Ao aprender programação, frequentemente lidamos com tarefas de forma linear e direta. Mas e se nos depararmos com um problema que exige dividi-lo em problemas menores e semelhantes? É aí que a recursão é utilizada.

Em termos simples, recursão é quando uma função chama a si mesma durante a sua execução. Isso pode parecer que criaria um loop infinito, mas se projetarmos nossa função corretamente, ela eventualmente alcançará um ponto em que não chama mais a si mesma.

Imagine uma boneca Matryoshka. Cada vez que você abre uma boneca, há uma menor dentro, e você continua até chegar à menor boneca que não pode ser aberta. Esse processo de abrir as bonecas é um pouco como recursão. Para chegar à menor boneca, que é como resolver o problema mais difícil, você resolve-o repetidamente resolvendo versões mais fáceis do mesmo problema (abrindo as bonecas maiores) até chegar a um ponto em que o problema não pode ser mais reduzido (a última boneca).

O processo de resolver um grande problema dividindo-o recursivamente em problemas menores até alcançar o menor/mais fácil possível é melhor compreendido com o conceito do “salto de fé recursivo”.

Salto de Fé Recursivo

Ao implementar uma solução recursiva para um problema, geralmente cria-se uma função que funciona chamando a si mesma em algum ponto. A parte de chamar a si mesma é normalmente referida como a chamada recursiva.

A grande vantagem das soluções recursivas é que se pode assumir que a função funciona corretamente quando chamada com alguns argumentos simples, e então implementar o comportamento correto para os mais complexos. Similar a chamar outras funções como sqrt, max, abs e outras que temos usado antes, você pode assumir que a função funciona para alguns argumentos menores/mais simples e chamá-los para construir o resultado atual com base neles.

Como demonstração de como se pode realizar um cálculo dentro de uma função recursiva, podemos tentar calcular a soma de todos os números de 0, 1, 2, ..., n, dado um número n.

Vamos implementar a função sum passo a passo. O primeiro passo é garantir que a função funcione corretamente para o caso mais simples (contar corretamente a soma quando n é 0 ou 1):

def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:         # No caso de n ser 0 => a soma é 0
        return 0       # Interrompe a execução da função aqui
    if n == 1:         # No caso de n ser 1 => a soma é 1
        return 1       # Interrompe a execução da função aqui

print(sum(1))          # sum(1) -> 1
print(sum(0))          # sum(0) -> 0
print(sum(2))          # sum(2) -> None (pois ainda não implementamos esta parte)

Tendo esta parte da função, já podemos usar o fato de que sum(0) sempre retornará 0 corretamente, enquanto sum(1) sempre retornará 1. A função funcionará corretamente mesmo se chamarmos a função sum com os argumentos 0 ou 1 a partir da própria função sum.

Assim, podemos ir um passo além e implementar a função sum para n = 2 e n = 3, utilizando os resultados de sum(1) e sum(0):

def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n == 2:             # Se n é 2, podemos adicionar 2 ao resultado de sum(1) implementado acima
        return n + sum(1)  # ou n + sum(n - 1)
    if n == 3:             # Se n é 3, podemos adicionar 3 ao resultado de sum(2) implementado acima
        return n + sum(2)  # ou n + sum(n - 1)

print(sum(1))          # sum(1) -> 1
print(sum(0))          # sum(0) -> 0
print(sum(2))          # sum(2) -> sum(1) -> 3
print(sum(3))          # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4))          # sum(4) -> None (pois ainda não implementamos esta parte)

Dessa forma, é evidente que a função sum funciona corretamente para casos simples como n igual a 0, 1, 2 ou 3.

Com isso, podemos implementar a função para outros valores de n maiores que 3. A única exigência é chegar a esses valores menores de n (0, 1, 2 ou 3) ao chamar a função sum de si mesma. Então, para valores maiores de n, como 4, 5 ou 6, etc., podemos implementar a função sum usando o fato de que, para calcular sum(4), podemos adicionar 4 ao resultado de sum(3), enquanto calcular sum(5) pode ser feito adicionando 5 ao resultado de sum(4):

def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return n + sum(1)
    if n == 3:
        return n + sum(2)
    # Para todos os outros casos (4, 5, 6, ...)
    return n + sum(n - 1)  

print(sum(2))          # sum(2) -> sum(1) -> 3
print(sum(3))          # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4))          # sum(4) -> sum(3) -> sum(2) -> sum(1) -> 10
# ...

As partes-chave de uma função recursiva são:

1. Caso base: uma condição que interrompe a recursão. Sem isso, a função chamaria a si mesma indefinidamente, causando um loop infinito.
   Aqui, é n == 0 e n == 1.

2. Passo recursivo: onde a função chama a si mesma, geralmente com um argumento diferente.
   Aqui, é sum(n - 1).

Como as chamadas para n == 1, n == 2 e n == 3 são exatamente as mesmas que para n == 4, n == 5, etc., podemos até simplificar a função sum tendo apenas um caso base (para n == 0):

def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:
        return 0
    return n + sum(n - 1)  

print(sum(2))          # sum(2) -> sum(1) -> sum(0) -> 3
print(sum(3))          # sum(3) -> sum(2) -> sum(1) -> sum(0) -> 6
print(sum(4))          # sum(4) -> sum(3) -> sum(2) -> sum(1) -> sum(0) -> 10
# ...

Dessa forma, tendo o salto de fé recursivo, assumimos/sabemos que a função funciona corretamente para casos menores/mais simples e construímos o restante da função com base nesses casos simples. Isso ajuda a entender como as funções recursivas funcionam e como podem ser implementadas.