Funções recursivas em Python

Neste tutorial, veremos o Recursão com exemplos em Python. A recursão na programação é uma técnica muito poderosa, ela é feita com funções que se autodenominam, veja isso como uma espécie de loop, já que o mesmo código será repetido várias vezes, até que a solução seja alcançada.

Características que uma função recursiva deve terCaso baseIsso nos permitirá encerrar a função em algum ponto, e que chamadas infinitas não ocorram.
Caso recursivoNesse caso, chamamos a função novamente, mas nos aproximaremos da solução. Ficará melhor nos exemplos.

ObservaçãoÉ importante ter clareza sobre o caso base e saber que o caso recursivo está se aproximando dele e não entra em um estado de chamadas infinitas, é um erro comum ao iniciar com recursão.

Vamos descer aos exemplos, que serão simples e curtos para que possam ser bem assimilados.

Exemplo 1 - Fatorial

Neste exemplo iremos resolver o fatorial de um númeroSe você quer saber do que se trata o fatorial, acesse este link. Aqui está o código, e abaixo eu explico a função recursiva.

 def fatorial (número): if (número == 0 ou número == 1): retorna 1 else: retorna número * fatorial (número-1) if __name__ == "__main__": try: num = int (input ("De De qual número você deseja saber o fatorial? ")) If (num <0): print (" O número deve ser maior ou igual a 0 ") else: print (" O fatorial de ", num," é ", fatorial (num)) exceto: print (" Um número é esperado ") 

Nossa função recursiva tem o caso base no if e o recursivo no else. Você pode ver que o caso base retorna 1 e que este é alcançado quando o parâmetro passado para a função é 0 ou 1, quando este caso é atingido, a função não chama novamente. No caso recursivo, temos uma chamada da função a si mesma, mas como você pode ver reduzindo o parâmetro em 1 (nos aproximamos do caso base). A última parte do código fora da função é responsável apenas por pedir ao usuário um número e verificar se é maior ou igual a 0 para chamar a função, já que o fatorial com números negativos não funciona.

Se fizermos a chamada para a função com o número 4, ou seja, fatorial (4), teremos as seguintes chamadas:

 Chamada 1: fatorial (4) Chamada 2: 4 * fatorial (3) Chamada 3: 3 * fatorial (2) Chamada 4: 2 * fatorial (1)

Ao chamar o fatorial com 1, não há mais chamadas e ele retornará 1, então essa função retorna retornando os resultados para a função que eu chamo, o retorno seria assim:

 fatorial (1) = 1 fatorial (2) = 2 * 1 fatorial (3) = 3 * 2 fatorial (4) = 4 * 6

E já temos nosso resultado, que é 24, da multiplicação dos números: 1 * 2 * 3 * 4. Em seguida, deixo uma captura de tela ao solicitar o fatorial de 5, que nada mais é do que multiplicar 5 pelo fatorial de 4 (que já sabemos é 24), resultando em 120. Você também pode ver que se o usuário inserir o número errado, é:

Exemplo 2 - Adição subtração

Neste exemplo eu coloquei uma função recursiva para fazer uma adição ou subtração, é claro que esse exemplo geralmente não ocorre na vida real, mas como exemplo funciona:

 def operar (número1, número2): if (número2 == 0): retornar número1 elif (número2 <0): retornar operar (número1-1, número2 + 1) else: retornar operar (número1 + 1, número2-1) se __name__ == "__main__": print ("Adicionando 10 e 3:", operar (10, 3)) print ("Adicionando 5 e -2:", operar (5, -2)) 

Aqui temos um caso base e 2 casos recursivos, trata-se de saber para que lado tocar, pois dependendo se o número for positivo ou negativo teremos que agir de forma diferente. A função de operação recebe 2 números, e o algoritmo se encarregará de subtrair ou adicionar um ao número2 e passá-lo para o número1 (Se o número2 for positivo, eu subtraio 1 do número2 e o adiciono ao número1), então até que a variável número2 seja igual a 0.

Por exemplo, vamos adicionar 3 + 2 vendo as chamadas.

 Chamada 1: operar (3,2) Chamada 2: operar (4,1) Chamada 3: operar (5,0)

Neste caso, quando conseguimos operar (5,0) não há mais nada a fazer, temos o resultado diretamente (ao contrário do caso do fatorial que teve que fazer a multiplicação). Aqui está o resultado da execução do código:

ObservaçãoEmbora com recursão tenhamos uma solução elegante e normalmente mais curta ela deve ser usada quando não temos outra opção, se conseguirmos puxar por sua variante iterativa será uma escolha melhor, já que consome menos memória e costuma ser mais rápida.

Gostou e ajudou este tutorial?Você pode recompensar o autor pressionando este botão para dar a ele um ponto positivo