Em palavras simples, a recursão é uma forma de resolver o problema fazendo com que uma função se chame, a palavra “ recursivo ”Origina-se do verbo latino“ recorrente ”, Que significa refazer algo. Isso é o que a função recursiva faz, ela refaz a mesma coisa repetidamente, ou seja, ela se recupera. Neste artigo, aprenderemos sobre recursão em python. A seguir estão os tópicos abordados neste blog:
- O que é recursão em Python?
- Condição de rescisão
- Limite de recursão do Python
- Achatamento de listas com recursão
- Vantagens de recursão
- Desvantagens da recursão
O que é recursão em Python?
Recursão é o processo de determinar algo em termos de si mesmo. Sabemos que em Python, qualquer função pode chamar qualquer outra função, uma função também pode chamar a si mesma. Esses tipos de funções que chamam a si mesmas até que determinada condição não seja atendida são denominados funções recursivas.
vamos dar alguns exemplos para ver como isso funciona. Se você receber um número inteiro positivo n, o fatorial seria.
- n! = n * (n-1) * (n-2) e assim por diante.
- 2! = 2 * (2-1)
- 1! = 1
- 0! = 0
- 4! = 4 * 3!
- 3! = 3 * 2!
- 2! = 2 * 1!
Substituir os valores acima resultará na seguinte expressão
- 4! = 4 * 3 * 2 * 1
Temos que definir uma função, digamos fato (n) que leva um inteiro positivo ou 0 como seu parâmetro e retorna o enésimo fatorial, como podemos fazer isso usando recursão?
melhor ide java para linux
Vamos ver, para fazer isso usando recursão, precisamos examinar a seguinte equação
n! = n. (n-1). (n-2) & hellip3.2.1
n! = n. (n-1)! # podemos reescrever a declaração acima como nesta linha
Agora, se passarmos 2 como parâmetro, obteremos:
2! = 2,1! = 2
Da mesma forma, se passarmos 1, obteremos:
1! = 1.0! = 1
Mas se passarmos 0, ele quebra
0! = 0. (- 1)! e aqui fatorial para -1 não está definido, então funciona apenas para valores> 0
Portanto, temos que escrever dois casos
1. n! = n. (n-1)! se n> = 1
2. 1 se n = 0
Esta é uma solução completa para todos os inteiros positivos e 0.
como usar a energia em java
Condição de rescisão
Uma função recursiva deve cumprir uma condição importante para terminar. Movendo-se em direção a uma condição em que o problema pode ser resolvido sem mais recursão, uma função recursiva será encerrada, minimizando o problema em subetapas menores. Uma recursão pode terminar em um loop infinito se a condição de encerramento não for atendida nas chamadas.
Condições fatoriais:
- fatorial de n = n * (n-1), desde que n seja maior que 1.
- 1 se n = 0
Vamos converter as condições fatoriais acima em código python:
def fact (n): if n == 1: return n else: return n * fact (n-1)
Vejamos um exemplo, digamos que queremos encontrar fatorial de 4:
fato (4) #isso retornará 4 * fato (3) e assim por diante até n == 1.
Resultado: 24
É usado com frequência como um exemplo de recursão devido à sua simplicidade e clareza. Resolver instâncias menores de um problema em cada etapa denominada como recursão na ciência da computação.
Limite de recursão do Python
Em algumas linguagens, você pode criar um loop recursivo infinito, mas, em Python, há um limite de recursão. Para verificar o limite, execute a seguinte função do módulo sys. que fornecerá o limite da recursão definida para python.
import sys sys.getrecursionlimit ()
Resultado: 1000
Você também pode alterar o limite usando functionsetrecursionlimit () do módulo sys de acordo com sua necessidade. Agora vamos criar uma função que se chama recursivamente até que exceda o limite e verifique o que acontece:
como criar um array de objetos em java
def recursive (): recursive () if __name__ == '__main__': recursive ()
Se você executar o código acima, obterá uma exceção de tempo de execução: RuntimeError: profundidade máxima de recursão excedida. Python impede que você crie uma função que termina em um loop recursivo sem fim.
Achatamento de listas com recursão
Outras coisas que você pode fazer usando recursão, exceto para fatoriais, digamos que você deseja criar um único a partir de uma lista que está aninhada, isso pode ser feito usando o código abaixo:
def flatten (a_list, flat_list = none): se flat_list for none: flat_list = [] para o item em a_list: se isinstance (item, lista): flatten (item, flat_list) else: flat_list.append (item) retornar flat_list se __name__ == '__main__': aninhado = [1,2,3, [4,5], 6] x = nivelado (aninhado) imprimir (x)
Resultado: [1,2,3,4,5,6]
A execução do código acima resultará em uma única lista em vez de uma lista de inteiros contendo uma lista de inteiros que usamos como entrada. Você também pode fazer a mesma coisa usando outras maneiras, Python tem algo chamado itertools.chain () você pode verificar o código usado para criar uma função chain () é uma abordagem diferente para fazer a mesma coisa que fizemos.
Vantagens de recursão
O código é limpo e elegante em uma função recursiva.
Uma tarefa composta pode ser dividida em subproblemas mais simples usando recursão.
Gerar sequência é mais fácil com recursão do que usar alguma iteração aninhada.
Desvantagens da recursão
Seguir a lógica por trás da função recursiva pode ser difícil às vezes.
Chamadas recursivas são caras (ineficientes) porque ocupam muita memória e tempo.
As funções recursivas são difíceis de depurar.
Neste artigo, vimos o que é recursão e como podemos desenvolver funções recursivas a partir da definição do problema, como matematicamente uma definição do problema pode ser definida. Resolvemos um problema do fatorial e descobrimos as condições necessárias para encontrar fatoriais a partir dos quais pudemos converter essas condições em código python, dando a você a compreensão de como funciona a recursão. Acho legal que o Python tenha um limite embutido para recursão para evitar que os desenvolvedores criem funções recursivas mal construídas. Uma coisa importante a notar é que a recursão é difícil de depurar, pois a função continua chamando a si mesma.