Recursão Python

Neste tutorial, você aprenderá a criar uma função recursiva (uma função que chama a si mesma).

O que é recursão?

A recursão é o processo de definir algo em termos de si mesmo.

Um exemplo do mundo físico seria colocar dois espelhos paralelos um de frente para o outro. Qualquer objeto entre eles seria refletido recursivamente.

Função recursiva do 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 como funções recursivas.

A imagem a seguir mostra o funcionamento de uma função recursiva chamada recurse .

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 (indicado 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 = 3
print("The factorial of", num, "is", factorial(num))

Saída

The factorial of 3 is 6

No exemplo acima, factorial() é uma função recursiva como chama a si mesma.

Quando chamamos essa função com um inteiro positivo, ela se chamará recursivamente diminuindo o número.

Cada função multiplica o número pelo fatorial do número abaixo dele até que seja igual a um. Essa chamada recursiva pode ser explicada nas etapas a seguir.

factorial(3)          # 1st call with 3
3 * factorial(2)      # 2nd call with 2
3 * 2 * factorial(1)  # 3rd call with 1
3 * 2 * 1             # return from 3rd call as number=1
3 * 2                 # return from 2nd call
6                     # return from 1st call

Vejamos uma imagem que mostra um processo passo a passo do que está acontecendo:

Nossa recursão termina quando o número é reduzido a 1. Isso é chamado de condição base.

Toda função recursiva deve ter uma condição base que pare a recursão ou então a função chama a si mesma infinitamente.

O interpretador Python limita a profundidade da recursão para ajudar a evitar recursões infinitas, resultando em estouros de pilha.

Por padrão, a profundidade máxima de recursão é 1000 . Se o limite for ultrapassado, resultará 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
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

Vantagens da Recursão

As funções recursivas tornam o código limpo e elegante.
Uma tarefa complexa pode ser dividida em subproblemas mais simples usando a 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.
Chamadas recursivas são caras (ineficientes), pois consomem muita memória e tempo.
Funções recursivas são difíceis de depurar.

Argumentos da função Python Função anônima/Lambda do Python

python