Recursão em

Sobre Recursão

A recursão é uma forma de executar código repetidamente dentro de uma função, fazendo com que a própria função se chame a si mesma. As funções que se chamam a si próprias são conhecidas como funções recursivas. A recursão pode ser vista como outra forma de fazer ciclos/iterar. E, tal como nos ciclos, usa-se uma expressão Boolean ou um teste True/False para determinar quando parar a execução recursiva.

Ao contrário dos ciclos, a recursão sem terminação em Python não pode correr infinitamente. Os valores usados em cada chamada à função são colocados no seu próprio frame na pilha do intérprete de Python. Se o número total de chamadas à função ocupar mais espaço do que a pilha tem disponível, isso resultará num erro.

Ciclos vs. implementação recursiva

Os ciclos e a recursão podem parecer semelhantes, no sentido em que ambos são iterativos. No entanto, aparentam ser diferentes, tanto ao nível do código como ao nível da implementação. Os ciclos podem ocorrer dentro do mesmo frame na pilha de chamadas. Normalmente, isto é gerido atualizando uma ou mais variáveis de forma a manter progressivamente o estado de cada iteração. É uma implementação eficiente, mas pode ficar um pouco confusa quando olhamos para o código.

A recursão, em vez de atualizar o estado das variáveis, pode passar valores atualizados diretamente como argumentos à chamada (iteração) seguinte da mesma função. Isto torna o corpo da função mais limpo e pode clarificar como acontece cada atualização. No entanto, também é uma implementação menos eficiente, porque cada chamada à mesma função acrescenta outro frame à pilha.

Recursão: porquê e porque não?

Se há o risco de provocar um erro ou um transbordo da pilha, porque é 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 compreender quando expressa através de recursão do que quando expressa através de ciclos. Também pode haver restrições do programa relacionadas com a utilização/mutação de dados, a gestão da complexidade, a delegação de responsabilidade ou a organização da carga de trabalho.

Os problemas que se prestam à recursão incluem problemas complexos mas repetitivos que se tornam mais pequenos ao longo do tempo, em particular os algoritmos de divisão e conquista e os algoritmos cumulativos. No entanto, devido ao limite de Python para o número de frames permitidos na pilha, nem todos os problemas beneficiam de uma estratégia totalmente recursiva. Os problemas menos adequados à recursão incluem os que têm um estado estável, mas precisam de se repetir durante um certo número de ciclos, os problemas que precisam de ser executados de forma assíncrona, e as situações que exigem um grande número de iterações.

Ciclos vs. estratégia recursiva: a insegurança da Indira

A Indira recebe a sua prestação mensal de segurança social por depósito automático na conta bancária, na segunda quarta-feira de cada mês. A Indira está preocupada em controlar o saldo do seu talão de cheques. Tem medo de passar cheques antes de o dinheiro ser depositado. Pede à sua neta Adya que lhe dê uma lista das datas em que o dinheiro aparecerá na sua conta.

A Adya, que está apenas a aprender a programar em Python, escreve um programa com base nos seus primeiros pensamentos. Quer devolver uma list com as datas de depósito, para que possam ser impressas. Quer escrever uma função que funcione para qualquer ano. Caso o calendário mude (ou caso outros familiares queiram que a Adya calcule os seus calendários de depósito), decide que a função precisa de um parâmetro adicional para o dia da semana. Por fim, a Adya decide que a função precisa de um parâmetro para indicar que dia da semana do mês é: o primeiro, o segundo, etc. Para todos estes requisitos, decide usar a classe date importada de datetime. Juntando tudo isto, a 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))

Esta primeira iteração funciona, mas a Adya pergunta-se se conseguirá refatorar o código de modo a usar menos linhas e menos ciclos aninhados. Também leu que é boa prática minimizar a mutação de estado, por isso gostaria de ver se consegue evitar mutar algumas das suas variáveis, como output, month e day_num.

Também conhece a recursão e pensa em como poderá alterar o seu programa para usar uma abordagem recursiva. As variáveis que são criadas e mutadas na sua função com ciclos poderiam, em vez disso, ser passadas como argumentos. Em vez de mutar as variáveis dentro da sua função, poderia passar valores atualizados como argumentos à chamada seguinte da função. Com essas intenções, 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, []))

A Adya fica contente por já não haver ciclos aninhados, nem estado mutado, e por ter menos 2 linhas de código!

Fica um pouco preocupada por a abordagem recursiva usar mais passos do que a abordagem com ciclos e, por isso, ser menos "performant". Mas reescrever o problema com recursão ajudou-a definitivamente a lidar com ciclos aninhados feios (um risco de desempenho), com muita mutação de estado e com confusão em torno de lógica condicional complexa. Também lhe parece mais "legível". Tem a certeza de que, quando voltar a este código depois de uma pausa, conseguirá lê-lo e lembrar-se mais facilmente do que ele faz.

No futuro, a Adya poderá tentar resolver os problemas primeiro de forma recursiva. Poderá achar mais fácil percorrer inicialmente o problema em passos claros quando o aninhamento, a mutação e a complexidade são minimizados. Depois de definir a lógica básica, pode então concentrar-se em otimizar os seus passos recursivos iniciais numa abordagem com ciclos mais eficiente.

Mais tarde ainda, quando aprender tuples, a Adya poderá considerar outras abordagens de "otimização", como usar uma list comprehension com Calendar.itermonthdates, ou fazer memoização de certos valores.

Variação recursiva: a chamada de cauda

Uma chamada de cauda ocorre quando a última instrução de uma função apenas se chama a si própria e nada mais. Este exemplo não é uma chamada de cauda, pois a função soma 1 ao resultado de se chamar a si própria:

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()

Isto vai imprimir:

The step is 1
The step is 2
retval is 3 after recursion

Para o refatorar numa chamada de cauda, torna 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()

Pode achar uma chamada de cauda ainda mais fácil de compreender do que uma chamada recursiva que não seja uma chamada de cauda. No entanto, ao usar recursão, é sempre importante saber que não haverá tantas iterações que provoquem o transbordo da pilha.

Limites da recursão em Python

Algumas linguagens conseguem otimizar as chamadas de cauda de modo a que cada chamada recursiva reutilize o frame da pilha da primeira chamada à função (de forma semelhante à maneira como um ciclo reutiliza um frame), em vez de acrescentar um frame adicional à pilha. Python não é uma dessas linguagens. Para se proteger contra o transbordo da pilha, Python tem um limite de recursão que, por predefinição, é de mil frames. É lançada uma exceção RecursionError quando o intérprete deteta 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 fará o programa rebentar, e possivelmente o sistema operativo.

Recursos

Para saberes mais sobre como usar a recursão em Python, podes começar por

• python-programming: recursion
• Real Python: python-recursion
• Real Python: python-thinking-recursively