Entendendo funções recursivas em Python

Como programador profissional, você precisa mandar muito bem no básico: variáveis, condicionais, tipos de dados, modificadores de acesso, chamadas de função, escopos etc. Não importa o tipo de programa que você esteja escrevendo — seja para Middleware, Desenvolvimento Web ou Data Science — esses são fundamentos que você precisa dominar. Antes de ser Data Scientist, Web Developer ou Machine Learning Engineer, você é programador.

Um desses conceitos fundamentais é a recursão, e entendê-la é crucial quando você escreve funções de determinado tipo. Você provavelmente já ouviu: "Chama-se recursão quando uma função chama a si mesma". Mas o que acontece nos bastidores? Como a memória física é afetada pela recursão? Dá para transformar qualquer função em uma função recursiva? Neste tutorial, você vai encontrar respostas para essas perguntas essenciais.

Anatomia de uma função recursiva:

Você talvez já tenha visto o termo recursão na graduação em Ciência da Computação ou TI. Aqui, vamos revisitar esses conceitos de um jeito mais interessante. Vamos lá.

Voltando à definição de recursão: "Chama-se recursão quando uma função chama a si mesma". Veja um exemplo que ilustra essa definição:

void A(n){
    if(n>=1){
        A(n-1);
        print(n);
    }
}

Perceba que a função A() está sendo chamada por ela mesma. Este é um exemplo de recursão, e A() é uma função recursiva.

Agora, vamos estudar alguns básicos de uma função recursiva.

Noções básicas de uma função recursiva:

Uma função recursiva precisa ter duas propriedades:

• Uma relação de recorrência
• Uma condição de parada

Considere o trecho de código acima para entender esses pontos. Claramente, a função segue uma relação de recorrência específica:

$n\le 1$ é a condição de parada / condição âncora / condição base, e, quando satisfeita, a recursão termina. É essencial especificar essa condição. Caso contrário, a função entra em um loop infinito.

(Observe que o trecho acima não segue uma linguagem específica. A intenção é apenas mostrar um exemplo de função recursiva.)

Talvez você esteja pensando: por que alguém escreveria uma função recursiva se existem alternativas melhores? Sim, às vezes é difícil rastrear uma recursão, mas com prática você vai achar a recursão elegante em termos de legibilidade e variáveis. A recursão não precisa de variáveis extras para ser executada, mas exige uma condição de parada bem definida. Muitas vezes é justamente essa condição que é difícil de encontrar. Ainda assim, "a prática leva à perfeição". Mais adiante, você verá como um programa pode ficar bonito e conciso quando implementado com recursão em vez de meios convencionais. Agora, vamos estudar a representação em memória de uma função recursiva.

Representação em memória de uma função recursiva:

Nesta seção, você vai ver como funções recursivas são representadas na memória por meio de árvores e pilhas. Considere a função recursiva A() a seguir para entender isso:

void A(n){
    if(n>=1){
        A(n-1);
        print(n);
    }
}

Primeiro, vamos entender a representação usando árvores. Pode parecer complicado, mas é direto. Se você desenhasse cada chamada de função como uma árvore, como ficaria?

Algo assim:

Alguns pontos importantes:

• A função é chamada com A(3) e, para isso, 4 chamadas (3+1) são feitas. Generalizando: se A(n) é chamada, são necessárias (n+1) chamadas no total.
• As chamadas P() representam as impressões produzidas por print(n).
• A função para em A(0), pois o if (após A(0)) recebe n < 1, o que faz a função terminar.

Começamos com a representação em árvore porque, para representar uma função recursiva em uma pilha, essa visualização ajuda. Veja a seguir.

(Uma pilha é uma estrutura de dados que segue a ordem LIFO — last in, first out.)

Para a representação em pilha, você precisa percorrer a árvore de cima para baixo e da esquerda para a direita. A imagem a seguir deixa isso claro.

Interpretando essa árvore: lembre que uma pilha tem duas operações — 1. Push, para inserir um elemento na pilha, e 2. Pop, para remover um elemento.

Agora, comece o percurso de cima para baixo e da esquerda para a direita:

• Sempre que vir uma chamada de função, faça push na pilha.
• Se vir uma chamada print()/P(), simplesmente imprima o elemento correspondente.

O resultado do percurso de A(3) até A(0) na ordem top-down gera os seguintes elementos na pilha:

Agora começa a segunda metade do percurso, isto é, a ordem esquerda-direita. Sempre que você encontrar uma chamada de função pela segunda vez, faça pop. Curiosamente, o primeiro elemento a sair da pilha (A(0)) foi o último a entrar (lembra do LIFO?). No caminho, você encontrará três chamadas P() — P(1), P(2) e P(3). Você vai imprimir na ordem em que aparecerem no percurso. A ordem será:

Ao finalizar o percurso, a pilha ficará totalmente vazia. Para entender ainda melhor a operação de pop, veja a imagem da pilha após esvaziar completamente.

Você viu como representar uma função recursiva simples na memória usando árvore e pilha. Agora, vamos ver como rastrear uma recursão.

Rastreando uma recursão:

Nesta seção, você vai aprender a rastrear uma recursão de forma metódica. Considere a função recursiva a seguir:

void A(n){
    if(n>0){
        print(n-1);
        A(n-1);
    }
}

Um ponto crucial: sempre que uma função é chamada, um registro de ativação é criado na memória contendo as variáveis locais dessa função e um ponteiro de instrução (que indica a próxima instrução a ser executada quando o controle voltar a essa função). Suponha que uma função main() chamou A() como A(3). Vamos numerar as linhas de A() a partir do if para facilitar:

void A(n){
    1. if(n>0)
    2. {
        3. print(n-1);
        4. A(n-1);
    5. }
}

Os registros de ativação ficariam assim:

Como dito, as funções têm suas cópias de variáveis locais e de ponteiros de instrução (neste caso, o número da linha). Após A(0), a função A() termina e começam os pops. Note que a pilha horizontal aqui é a mesma que você viu anteriormente no tutorial. Enquanto os registros são empilhados, as impressões também acontecem, e os seguintes elementos serão impressos:

Os ponteiros de instrução são vitais aqui porque, em funções recursivas, o controle volta para a mesma função, mas com valores diferentes de variáveis. Para manter tudo sincronizado, esses ponteiros ajudam muito. Você pode seguir exatamente esse processo para rastrear uma recursão usando a representação em árvore.

Agora, vamos estudar como fazer a análise de espaço e tempo de uma função recursiva.

Análise de espaço-tempo de uma função recursiva:

A DataCamp tem um excelente artigo sobre análise assintótica em Python, e vale a pena conferir antes desta seção. Vamos recapitular rapidamente o que são as análises de espaço e tempo de uma função (também conhecidas como complexidade de espaço e complexidade de tempo):

Para uma entrada qualquer, uma função deve produzir uma saída. Para isso, quanto tempo a função leva? A complexidade de tempo aproxima esse tempo, também chamada de runtime da função. Da mesma forma, a complexidade de espaço aproxima o espaço (memória) necessário para uma função, dado uma entrada. Mas por que isso é útil?

• Em vez de executar uma função em vários tamanhos de entrada, você consegue aproximar como ela se comporta conforme a entrada cresce.
• Se você tem duas funções que cumprem o mesmo objetivo, qual escolher? Quais critérios usar? Isso mesmo: comparar as complexidades de espaço e tempo para ver qual tem melhor desempenho.

Vamos pegar uma função recursiva simples e analisar suas complexidades de tempo e de espaço.

void A(n){
    if(n>1) // Anchor condition
    {
       return A(n-1);
    }
}

Começando pela complexidade de tempo. Suponha que o tempo total da função A() seja $T(n)$. Então, $T(n)$ é a soma do tempo de comparar se n é maior que 1 e do tempo para executar A(n-1). Assim, $T(n)$ pode ser expresso como:

O 1 representa o tempo da comparação (poderia ser qualquer constante). Agora, qual é o tempo (em termos de $T(n)$) para executar A(n-1)?

Da mesma forma,

e assim por diante.

Se você observar bem, todas as equações estão conectadas, certo? Substituindo uma na outra, temos:

$T(n)$ = 1 + (1 + $T(n-2)$) = 2 + $T(n-2)$ = 3 + $T(n-3)$ = .... = k + $T(n-k)$ (após rodar a função por k termos)

Agora, precisamos saber quando a função vai parar. Pela condição âncora dada, podemos escrever:

Suponha que, após k termos, a função pare. Então deve ser:

$n - k = 1 => k = n - 1$

Substituindo k (= n - 1) em $T(n) = k + T(n-k)$:

$T(n) = (n-1) + T(n-(n-1))$
$=> T(n) = (n-1) + T(1)$
$=> T(n) = n-1 + 1 = n$ // Para T(1), só há comparação

Pela análise assintótica, $T(n) = n$ pode ser escrito como $T(n) = \mathcal{O}(n)$. Isso significa que a complexidade de tempo (pior caso) da função é $\mathcal{O}(n)$.

Vale desacelerar aqui e revisar cada passo com calma. É altamente recomendado fazer no papel para entender tudo direitinho.

A análise de espaço desta função é simples. A função roda em memória e não usa variáveis extras. Logo, podemos concluir que a complexidade de espaço da função é $\mathcal{O}(n)$.

Agora vamos juntar tudo isso e implementar uma função recursiva simples em Python.

Implementando uma função recursiva simples em Python:

Vamos escrever uma função recursiva para calcular o fatorial de um número. Em seguida, escrever a versão iterativa da mesma função. Vamos lá.

# Função recursiva factorial_recursion()

def factorial_recursion(n):  
   if n == 1:  
       return n  
   else:  
       return n*factorial_recursion(n-1)

# Chamar a função

num = 7
print("The factorial of ",num," is ",factorial_recursion(num))

The factorial of  7  is  5040

Lembra dos dois ingredientes-chave para escrever uma função recursiva?

• Relação de recorrência
• Condição de parada

Neste caso, a relação de recorrência pode ser:

$f(n) = n!$
$f(n) = n * f(n-1)$ e assim por diante.

A condição de parada é quando n é igual a 1.

Simples, né?

Agora, implemente a versão iterativa da mesma função.

def factorial_iterative(num):
    factorial = 1
    if num < 0:
        print("Sorry, factorial does not exist for negative numbers")
    elif num == 0:
        print("The factorial of 0 is 1")
    else:
        for i in range(1,num + 1):
           factorial = factorial*i
        print("The factorial of",num,"is",factorial)

factorial_iterative(7)

The factorial of 7 is 5040

Dá para notar a diferença entre as duas versões. A recursiva fica bem mais elegante do que a iterativa, não acha?

Parabéns!

Você chegou ao fim. Neste tutorial, você fez um estudo aprofundado de funções recursivas. Começamos do zero e chegamos à análise das complexidades de tempo e espaço. Você também viu como a recursão pode ser vantajosa para problemas com certas características. Agora, você já está pronto para resolver problemas (com relação de recorrência e condição de parada) usando recursão. Uma boa prática é resolver o problema dos números de Fibonacci em um intervalo usando recursão.

Eu recomendo fortemente que você resolva problemas clássicos como busca binária, merge sort, Torre de Hanói etc. usando recursão e faça também a análise de espaço-tempo. Isso certamente vai te tornar um programador melhor.

Para uma introdução, o que vimos aqui é suficiente. Mas, se quiser estudar mais sobre recursão, confira os links a seguir:

• Recursion and Dictionaries, por Prof. Grimson
• Programação dinâmica para otimizar o desempenho de funções recursivas

Se quiser aprender mais sobre Python, faça o curso gratuito da DataCamp Intro to Python for Data Science.