O que é recursão?
recursão é o processo de definir algo em termos de si mesmo.um exemplo do mundo físico seria colocar dois espelhos paralelos voltados um para o outro. Qualquer objeto entre eles seria refletido recursivamente.
função recursiva em Python
em Python, sabemos que uma função pode chamar outras funções. É mesmo possível que a função se chame a si mesma. Estes tipos de construção são denominados como funções recursivas.
A imagem seguinte mostra o funcionamento de uma função recursiva chamada .
a Seguir está um exemplo de uma função recursiva para encontrar o fatorial de um número inteiro.
Factorial de um número é o produto de todos os inteiros de 1 a esse número. Por exemplo, o factorial de 6 (denotado como 6!) é 1*2*3*4*5*6 = 720.
Exemplo de uma 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 = 3print("The factorial of", num, "is", factorial(num))Saída
The factorial of 3 is 6
No exemplo acima, factorial() é uma função recursiva como ele chama a si mesmo.
Quando vamos chamar esta função com um número inteiro positivo, ele irá recursivamente chamar a si, diminuindo o número.
cada função multiplica o número com o factorial do número abaixo até que seja igual a um. Esta chamada recursiva pode ser explicada nos seguintes passos.
factorial(3) # 1st call with 33 * factorial(2) # 2nd call with 23 * 2 * factorial(1) # 3rd call with 13 * 2 * 1 # return from 3rd call as number=13 * 2 # return from 2nd call6 # return from 1st call
Vamos olhar para uma imagem que mostra um passo-a-passo do que está acontecendo:
a Nossa recursão termina quando o número reduz para 1. Isto é chamado de condição base.
cada função recursiva deve ter uma condição de base que pare a recursão ou então a função se chama infinitamente.
o interpretador de Python limita as profundezas da recursão para ajudar a evitar recursões infinitas, resultando em fluxos de pilha.
Por padrão, a profundidade máxima da recursão é 1000. Se o limite for cruzado, resulta em RecursionError. Vejamos uma dessas condições.
def recursor(): recursor()recursor()Saída
Traceback (most recent call last): File "<string>", line 3, in <module> File "<string>", line 2, in a File "<string>", line 2, in a File "<string>", line 2, in a RecursionError: maximum recursion depth exceeded
> Vantagens da Recursão
- funções Recursivas tornar o código olhar limpo e elegante.
- uma tarefa complexa pode ser dividida em sub-problemas mais simples usando recursão.
- A Geração de sequência é mais fácil com recursão do que usando 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 consomem muita memória e tempo.as funções recursivas são difíceis de depurar.