Sobre Recursão
A recursão é uma forma de executar código repetidamente dentro de uma função, fazendo com que a função chame a si mesma.
Funções que chamam a si mesmas são conhecidas como funções recursivas.
A recursão pode ser vista como outra maneira de fazer um laço/iterar.
E, assim como no laço, uma expressão Boolean ou um teste com True/False é usado para determinar quando parar a execução recursiva.
Diferente do laço, a recursão sem terminação em Python não consegue rodar indefinidamente.
Os valores usados em cada chamada de função são colocados em seu próprio quadro na pilha do intérprete do Python.
Se o número total de chamadas de função ocupar mais espaço do que a pilha comporta, isso vai resultar em um erro.
Laço vs implementação recursiva
O laço e a recursão podem parecer parecidos, já que ambos são iterativos.
No entanto, eles têm aparência diferente, tanto no nível do código quanto no nível da implementação.
O laço pode acontecer dentro do mesmo quadro na pilha de chamadas.
Isso normalmente é gerenciado atualizando um ou mais valores de variáveis para manter progressivamente o estado a cada iteração.
É uma implementação eficiente, mas pode ficar um pouco confusa quando olhamos o código.
A recursão, em vez de atualizar o estado das variáveis, pode passar valores atualizados diretamente como argumentos para a próxima chamada (iteração) da mesma função.
Isso deixa o corpo da função mais limpo e pode deixar mais claro como cada atualização acontece.
No entanto, também é uma implementação menos eficiente, já que cada chamada à mesma função adiciona outro quadro à pilha.
Recursão: por que sim e por que não?
Se existe o risco de causar um erro de pilha ou estouro, por que alguém usaria uma estratégia recursiva para resolver um problema?
Legibilidade, rastreabilidade e intenção.
Pode haver situações em que uma solução é mais legível e/ou mais fácil de raciocinar quando expressa por meio da recursão do que por meio do laço.
Também pode haver restrições do programa quanto a usar/mutar dados, gerenciar complexidade, delegar responsabilidade ou organizar cargas de trabalho.
Entre os problemas que se prestam à recursão estão problemas complexos, mas repetitivos, que diminuem ao longo do tempo, especialmente algoritmos de divisão e conquista e algoritmos cumulativos.
No entanto, devido ao limite do Python para quantos quadros são permitidos na pilha, nem todos os problemas vão se beneficiar de uma estratégia totalmente recursiva.
Problemas menos adequados à recursão incluem os que têm um estado estável, mas precisam se repetir por um certo número de ciclos, problemas que precisam ser executados de forma assíncrona e situações que exigem um grande número de iterações.
Indira recebe o pagamento mensal da Previdência Social automaticamente em sua conta bancária toda segunda quarta-feira do mês.
Indira está preocupada em conciliar seu talão de cheques.
Ela tem medo de emitir cheques antes de o dinheiro ser depositado.
Ela pede à sua neta Adya que faça uma lista das datas em que o dinheiro vai aparecer na sua conta.
Adya, que está apenas aprendendo a programar em Python, escreve um programa com base nas suas primeiras ideias.
Ela quer retornar uma list com as datas de depósito para que possam ser impressas.
Ela quer escrever uma função que funcione para qualquer ano.
Caso o calendário mude (ou caso outros parentes queiram que Adya calcule seus calendários de depósito), ela decide que a função precisa receber um parâmetro adicional para o dia da semana.
Por fim, Adya decide que a função precisa de um parâmetro para qual dia da semana do mês é: o primeiro, o segundo etc.
Para todos esses requisitos, ela decide usar a classe date importada de datetime.
Juntando tudo isso, Adya chega a:
from datetime import date
def paydates_for_year(year, weekday, ordinal):
"""Returns a list of the matching weekday dates.
Arguments:
year (int): The year (e.g. 2022).
weekday (int): The weekday number (e.g. 3 for Wednesday).
ordinal (int): Which weekday of the month (e.g. 2 for the second day).
Returns:
output (list): Matching weekday dates.
"""
output = []
for month in range(1, 13):
for day_num in range(1, 8):
if date(year, month, day_num).isoweekday() == weekday:
output.append(date(year, month, day_num + (ordinal - 1) * 7))
break
return output
# find the second Wednesday of the month for all the months in 2022
print(paydates_for_year(2022, 3, 2))
Essa primeira iteração funciona, mas Adya se pergunta se consegue refatorar o código para usar menos linhas e menos laços aninhados.
Ela também leu que é bom minimizar a mutação de estado, então gostaria de ver se consegue evitar mutar algumas de suas variáveis, como output, month e day_num .
Ela também conhece a recursão e pensa em como poderia mudar seu programa para usar uma abordagem recursiva.
As variáveis criadas e mutadas na sua função com laço poderiam, em vez disso, ser passadas como argumentos.
Em vez de mutar as variáveis dentro da sua função, ela poderia passar valores atualizados como argumentos para a próxima chamada da função.
Com essas intenções, ela chega a esta abordagem recursiva:
from datetime import date
def paydates_for_year_rec(year, weekday, ordinal, month, day_num, output):
"""Returns a list of the matching weekday dates
Arguments:
year (int): The year (e.g. 2022).
weekday (int): The weekday number (e.g. 3 for Wednesday).
ordinal (int): Which weekday of the month (e.g. 2 for the second day).
month (int): The month number currently being processed.
day_num (int): The day number of the month currently being processed.
Returns:
output (list): Matching weekday dates.
"""
if month == 13:
return output
if date(year, month, day_num).isoweekday() == weekday:
return paydates_for_year_rec(
year, weekday, ordinal, month + 1, 1, output
+ [date(year, month, day_num + (ordinal - 1) * 7)]
)
return paydates_for_year_rec(year, weekday, ordinal, month, day_num + 1, output)
# find the second Wednesday of the month for all the months in 2022
print(paydates_for_year_rec(2022, 3, 2, 1, 1, []))
Adya fica feliz por não haver mais laços aninhados, nem estado mutado, e por ter 2 linhas de código a menos!
Ela fica um pouco preocupada por a abordagem recursiva usar mais passos do que a abordagem com laço e, por isso, ser menos "performática".
Mas reescrever o problema usando recursão com certeza a ajudou a lidar com laços aninhados feios (um risco de desempenho), muita mutação de estado e confusão em torno de uma lógica condicional complexa.
Também parece mais "legível": ela tem certeza de que, quando voltar a esse código depois de uma pausa, conseguirá lê-lo e lembrar com mais facilidade o que ele faz.
No futuro, Adya pode tentar resolver os problemas primeiro de forma recursiva.
Ela pode achar mais fácil percorrer o problema inicialmente em passos claros quando o aninhamento, a mutação e a complexidade são minimizados.
Depois de resolver a lógica básica, ela pode então se concentrar em otimizar seus passos recursivos iniciais e transformá-los em uma abordagem com laço mais performática.
Mais adiante, quando aprender sobre tuples, Adya poderá considerar outras abordagens de "otimização", como usar uma list comprehension com Calendar.itermonthdates ou memoizar certos valores.
Variação recursiva: a chamada de cauda
Uma chamada de cauda acontece quando a última instrução de uma função apenas chama a si mesma e nada mais.
Este exemplo não é uma chamada de cauda, pois a função soma 1 ao resultado da chamada a si mesma:
def print_increment(step, max_value):
if step > max_value:
return 1
print(f'The step is {step}')
return 1 + print_increment(step + 1, max_value)
def main():
retval = print_increment(1, 2)
print(f'retval is {retval} after recursion')
if __name__ == "__main__":
main()
Isso vai imprimir:
The step is 1
The step is 2
retval is 3 after recursion
Para refatorá-lo para uma chamada de cauda, torne retval um parâmetro de print_increment.
def print_increment(step, max_value, retval):
if step > max_value:
return retval
print(f'The step is {step}')
return print_increment(step + 1, max_value, retval + 1)
def main():
retval = print_increment(1, 2, 1)
print(f'retval is {retval} after recursion')
if __name__ == "__main__":
main()
Você pode achar uma chamada de cauda ainda mais fácil de raciocinar do que uma chamada recursiva que não é uma chamada de cauda.
No entanto, ao usar recursão, é sempre importante saber que não haverá tantas iterações a ponto de a pilha estourar.
Limites de recursão em Python
Algumas linguagens conseguem otimizar chamadas de cauda de modo que cada chamada recursiva reutilize o quadro de pilha da primeira chamada à função (parecido com a forma como um laço reutiliza um quadro), em vez de adicionar outro quadro à pilha.
Python não é uma dessas linguagens.
Para se proteger contra estouro de pilha, o Python tem um limite de recursão que, por padrão, é de mil quadros.
Uma exceção RecursionError é lançada quando o intérprete detecta que o limite de recursão foi excedido.
É possível usar o método sys.setrecursionlimit para aumentar o limite de recursão, mas fazer isso corre o risco de provocar uma falha de segmentação em tempo de execução que vai travar o programa e, possivelmente, o sistema operacional.
Recursos
Para aprender mais sobre como usar recursão em Python, você pode começar com
{one: "1 exercício", many: "%{count} de exercícios", other: "%{count} exercícios"}
