Entendendo Recursão em Python: E aí, vai encarar?

Recursão é um conceito fundamental em programação, mas às vezes pode parecer meio misterioso. Então, vamos dar uma boa simplificada nisso e ver que é mais fácil do que parece!

O que é Recursão?

Recursão é quando uma função resolve um problema chamando... ela mesma! Sim, é isso mesmo. Funciona como uma história que você conta repetidamente, só que a cada vez um pouquinho menor até chegar ao fim. Mas para ela funcionar direitinho, precisa atender a duas regrinhas de ouro:

1. Condição de Término: é o ponto onde a função deve parar, senão ela fica num loop eterno (não queremos isso, né?).
2. Autochamada: é quando a função chama a si mesma, indo cada vez mais fundo até chegar na condição de término.

Agora, vamos ver como isso funciona na prática!

Como Funciona?

Para explicar melhor, nada melhor que o clássico exemplo do fatorial! Imagine que queremos calcular (5!) (leia-se "cinco fatorial"). Como funciona?

5! = 5 * 4 * 3 * 2 * 1!

No entanto, com recursão, podemos pensar nisso assim:

5! = 5 * 4!

E, na sequência, 4! é (4 * 3!), e assim por diante, até que chegamos a (1!), que é o nosso caso base (a condição de término).

Exemplo Prático: Fatorial

Vamos para o código, porque é aí que o conceito ganha vida! Aqui está o famoso cálculo do fatorial usando recursão:

def fatorial(numero):
    if numero == 0 or numero == 1:
        return 1  # caso base
    else:
        return numero * fatorial(numero - 1)

Explicação:

1. O caso base aqui é quando o número é 0 ou 1, onde a função simplesmente retorna 1.
2. Se o número for maior que 1, a função se chama com numero - 1, acumulando os valores até o caso base.

Complexidade

• Tempo: (O(n)) — pois há n chamadas recursivas.
• Espaço: (O(n)) — a profundidade da pilha de execução é n.

Exemplo Prático: Fibonacci

Outro exemplo muito usado é a sequência de Fibonacci. Ela é assim:

f(0) = 0, f(1) = 1, f(n) = f(n - 1) + f(n - 2)

Vamos para o código!

def seq_fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n > 1:
        return seq_fib(n - 1) + seq_fib(n - 2)

Complexidade de Fibonacci:

• Tempo: (O(2^n)) — exponencial! ⚠️
• Espaço: (O(n)) — uso de pilha para as chamadas recursivas.

Por isso que, para grandes valores, o cálculo de Fibonacci com recursão pura pode ser meio pesado. Mas, para fins de aprendizado, é um ótimo exemplo!

Finalmente

Recursão é um conceito chave na programação e, apesar de parecer um pouco intimidante no começo, fica muito mais fácil com a prática. Esses exemplos de fatorial e Fibonacci são apenas o início!

Se quiser praticar, de uma conferida e faça uma cópia , nesse Colab aqui!