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.💡
A única exigência é garantir que a função chegará ao caso base (o caso mais simples). Caso contrário, teríamos uma função recursiva que executaria indefinidamente e poderíamos ter um StackOverflow!
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:
- 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 == 0en == 1.
- 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.
💡
Chamar a função recursivamente é como chamar uma função completamente diferente que você sabe com certeza que funcionará com os argumentos passados.