O que é função recursiva?
A função chama a si mesma repetidamente até satisfazer uma condição recursiva. Uma função de recursão divide o problema em problemas menores e chama sua própria lógica para resolver o problema menor. Essa técnica é conhecida como dividir e conquistar. É usado na matemática e no campo da ciência da computação.
A função recursiva inclui uma caixa base (ou caixa terminal) e uma caixa recursiva. No caso base, você pode considerar o principal problema a ser resolvido e o caso recursivo divide o problema em partes menores até atingir um nível em que possa ser resolvido rapidamente. Um caso recursivo pode retornar um resultado ou pode se chamar novamente para dividir ainda mais o problema. Cada vez que o problema se decompõe em um problema menor, a função que está sendo chamada recursivamente salva o estado da chamada e espera o resultado por si próprio após a decomposição do problema.
Função Recursiva em Python
O conceito de recursão permanece o mesmo em Python. A função chama a si mesma para dividir o problema em problemas menores. O exemplo mais simples que poderíamos pensar em recursão seria encontrar o fatorial de um número.
Digamos que precisamos encontrar o fatorial do número 5 => 5! (Nosso problema)
Para encontrar 5! o problema pode ser dividido em outros menores 5! => 5 x 4!
Então, para obter 5! Precisamos encontrar 4! e multiplique por 5.
Vamos continuar dividindo o problema
5! = 4! x 5
4! = 3! x 4
3! = 3 x 2!
2! = 2 x 1!
1! = 1
Quando atinge o menor pedaço, ou seja, obtendo o fatorial 1, podemos retornar o resultado como
Vamos dar um exemplo de pseudo-código: -
Algoritmo para fatorial
Vamos ver o algoritmo para fatorial:
function get_factorial( n ):
if n < 2:
return 1
else:
return get_factorial(n -1)
Chamadas de função
Suponha que estamos encontrando um fatorial de 5.
get_factorial(5) 5 * get_factorial(4) = returns 120 #1st call
get_factorial(4) 4 * get_factorial(3) = returns 24 #2nd call
get_factorial(3) 3 * get_factorial(2) = returns 6 #3rd call
get_factorial(2) 2 * get_factorial(1) = returns 2 #4th call
get_factorial(1) returns 1 #5th call
O resultado final será 120, onde iniciamos a execução da função. Nossa função de recursão para quando o número é tão reduzido que o resultado pode ser obtido.
- A primeira chamada que está obtendo o fatorial 5 resultará em uma condição recursiva na qual será adicionada à pilha e outra chamada será feita após a redução do número para 4.
- Essa recursão continuará chamando e dividindo o problema em partes menores até atingir a condição de base.
- A condição básica aqui é quando o número é 1.
- Toda função recursiva tem sua própria condição recursiva e uma condição básica.
Prós e contras da função recursiva do Python
- A execução da recursão é para que ele não faça nenhum cálculo até atingir a condição base.
- Ao chegar às condições básicas, você pode ficar sem memória.
- Em um grande problema em que pode haver um milhão de etapas ou podemos dizer que um milhão de recursões para executar o programa pode acabar causando erro de memória ou falha de segmentação.
- 1000000! = 1000000 * 999999! =?
- A recursão é diferente da iteração e não é escalada como um método iterativo.
- Idiomas diferentes têm otimizações diferentes para recursão.
- Em muitos idiomas, o método iterativo teria um desempenho melhor que a recursão.
- Todo idioma tem algumas restrições sobre a profundidade da recursão que você pode enfrentar ao resolver grandes problemas.
- Às vezes, é difícil entender os problemas complexos da recursão, ao passo que é bastante simples com a iteração.
Alguns profissionais
- Em alguns casos, a recursão é uma maneira conveniente e rápida de usar.
- Muito útil na travessia da árvore e na pesquisa binária.
Código Python - Recursão vs Iteração
Entendemos o que é recursão e como funciona em Python, pois sabemos que todas as linguagens têm diferentes implementações de recursão para otimizações de memória e computacionais. Pode haver um caso em que a iteração seja mais rápida que a recursão.
Aqui, compararíamos o método de recursão e iteração para ver o desempenho do Python nos dois casos.
1. Código de Recursão para Fatorial
def get_recursive_factorial(n):
if n < 0:
return -1
elif n < 2: #base condition
return 1
else:
return n * get_recursive_factorial(n -1) #recursion condition
2. Problema fatorial usando iteração (loop)
def get_iterative_factorial(n):
if n < 0:
return -1
else:
fact = 1
for i in range( 1, n+1 ):
fact *= i
return fact
3. Resultados da impressão
print(get_recursive_factorial(6))
print(get_iterative_factorial(6))
Resultado:
Como podemos ver, ambos dão a mesma saída que escrevemos a mesma lógica. Aqui não podemos ver nenhuma diferença na execução.
Vamos adicionar um código de tempo para obter mais informações sobre a execução da recursão e iteração no Python.
Importaremos a biblioteca "time" e verificaremos quanto tempo a recursão e a iteração levam para retornar o resultado.
4. Código com cálculo de tempo
import time
def get_recursive_factorial(n):
if n < 0:
return -1
elif n < 2:
return 1
else:
return n * get_recursive_factorial(n-1)
def get_iterative_factorial(n):
if n < 0 :
return -1
else:
fact = 1
for i in range(1, n+1):
fact *= i
return fact
start_time = time.time()
get_recursive_factorial(100)
print("Recursion--- %s seconds ---" % (time.time() - start_time))
start_time = time.time()
get_iterative_factorial(100)
print("Iteration--- %s seconds ---" % (time.time() - start_time))
Faremos execuções repetidas com um valor diferente para fatorial e veremos os resultados. Os resultados abaixo podem variar de máquina para máquina. Nós usamos o MacBook Pro de 16 GB de RAM i7.
Estamos usando Python 3.7 para execução
Caso 1: - Fatorial de 6:
Caso 2: Fatorial de 50:
Caso 3: Fatorial de 100:
Caso 4: Fatorial de 500:
Caso 5: Fatorial de 1000:
Analisamos os dois métodos em um problema diferente. Além disso, ambos tiveram desempenho semelhante, exceto no caso 4.
No caso 5, obtivemos um erro ao fazê-lo com recursão.
O Python tem uma restrição na profundidade máxima que você pode usar com recursão, mas o mesmo problema eu consegui resolver com iteração.
Python tem restrições contra o problema de estouro. Python não é otimizado para recursão de cauda, e recursão descontrolada causa um estouro de pilha.
A função “sys.getrecursionlimit ()” informava o limite de recursão.
O limite de recursão pode ser alterado, mas não recomendado; pode ser perigoso.
Conclusão - Função Recursiva do Python
- A recursão é uma solução útil para alguns problemas, como travessia de árvore e outros problemas.
- Python não é uma linguagem de programação funcional e podemos ver que a pilha de recursão não é tão otimizada em comparação com a iteração.
- Devemos usar a iteração em nosso algoritmo, pois ela é mais otimizada em Python e oferece melhor velocidade.
Artigos recomendados
Este é um guia para a função recursiva em Python. Aqui discutimos o que é função recursiva, função recursiva em Python, algoritmo para fatorial etc. Você também pode consultar nossos outros artigos sugeridos para saber mais.
- Fatorial em Python
- Comandos do Spark Shell
- Melhores Compiladores C
- Tipos de algoritmos
- Programa fatorial em JavaScript
- Guia para a lista de comandos do Unix Shell
- Tipos de formulários em reagir com exemplos