This content originally appeared on DEV Community and was authored by Isis Araujo
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:
- 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é?).
- 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:
- O caso base aqui é quando o número é
0ou1, onde a função simplesmente retorna1. - Se o número for maior que
1, a função se chama comnumero - 1, acumulando os valores até o caso base.
Complexidade
-
Tempo: (O(n)) — pois há
nchamadas 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!
This content originally appeared on DEV Community and was authored by Isis Araujo
Isis Araujo | Sciencx (2024-10-27T04:21:07+00:00) Entendendo Recursão em Python: E aí, vai encarar?. Retrieved from https://www.scien.cx/2024/10/27/entendendo-recursao-em-python-e-ai-vai-encarar/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.