Neste tutorial, você aprenderá a criar uma função recursiva (uma função que chama a si mesma).
O que é recursão?
Recursão é o processo de definir algo em termos de si mesmo.
Um exemplo de mundo físico seria colocar dois espelhos paralelos voltados um para o outro. Qualquer objeto entre eles seria refletido recursivamente.
Função recursiva Python
Em Python, sabemos que uma função pode chamar outras funções. É até possível que a função chame a si mesma. Esses tipos de construção são denominados funções recursivas.
A imagem a seguir mostra o funcionamento de uma função recursiva chamada recurse.
Função recursiva em Python
A seguir está um exemplo de uma função recursiva para encontrar o fatorial de um inteiro.
O fatorial de um número é o produto de todos os inteiros de 1 a esse número. Por exemplo, o fatorial de 6 (denotado como 6!) É 1 * 2 * 3 * 4 * 5 * 6 = 720.
Exemplo de função recursiva
def factorial(x): """This is a recursive function to find the factorial of an integer""" if x == 1: return 1 else: return (x * factorial(x-1)) num = 3 print("The factorial of", num, "is", factorial(num))
Resultado
O fatorial de 3 é 6
No exemplo acima, factorial()é uma função recursiva , uma vez que se chama.
Quando chamamos esta função com um número inteiro positivo, ela se chamará recursivamente diminuindo o número.
Cada função multiplica o número pelo fatorial do número abaixo dela até que seja igual a um. Essa chamada recursiva pode ser explicada nas etapas a seguir.
fatorial (3) # 1ª chamada com 3 3 * fatorial (2) # 2ª chamada com 2 3 * 2 * fatorial (1) # 3ª chamada com 1 3 * 2 * 1 # retorno da 3ª chamada como número = 1 3 * 2 # retorno da 2ª chamada 6 # retorno da 1ª chamada
Vejamos uma imagem que mostra um processo passo a passo do que está acontecendo:
Trabalho de uma função fatorial recursiva
Nossa recursão termina quando o número se reduz a 1. Isso é chamado de condição de base.
Cada função recursiva deve ter uma condição básica que interrompa a recursão, ou então a função se auto-chama infinitamente.
O interpretador Python limita as profundidades de recursão para ajudar a evitar recursões infinitas, resultando em estouro de pilha.
Por padrão, a profundidade máxima de recursão é 1000. Se o limite for ultrapassado, resulta em RecursionError. Vejamos uma dessas condições.
def recursor(): recursor() recursor()
Resultado
Traceback (última chamada mais recente): Arquivo "", linha 3, em Arquivo "", linha 2, em um Arquivo "", linha 2, em um Arquivo "", linha 2, em a (Linha anterior repetida mais 996 vezes ) RecursionError: profundidade máxima de recursão excedida
Vantagens da recursão
- Funções recursivas fazem o código parecer limpo e elegante.
- Uma tarefa complexa pode ser dividida em subproblemas mais simples usando recursão.
- A geração de sequência é mais fácil com recursão do que usar alguma iteração aninhada.
Desvantagens da Recursão
- Às vezes, a lógica por trás da recursão é difícil de seguir.
- As chamadas recursivas são caras (ineficientes), pois ocupam muita memória e tempo.
- As funções recursivas são difíceis de depurar.
