Funções recursivas do Python

Resumo: neste tutorial, você aprenderá sobre as funções recursivas do Python e como usá-las para simplificar seu código.

Introdução às funções recursivas

Uma função recursiva é uma função que chama a si mesma até que não o faça.

A função fn() a seguir é uma função recursiva porque tem uma chamada para si mesma:

def fn():
    # ...
    fn()
    # ...

Na função fn(), o #... significa outro código.

Além disso, uma função recursiva precisa ter uma condição para parar de chamar a si mesma. Então você precisa adicionar uma instrução if como esta:

def fn():
    # ...
    if condition:
        # stop calling itself
    else:
        fn()
    # ...

Normalmente, você usa uma função recursiva para dividir um grande problema que é difícil de resolver em problemas menores que são mais fáceis de resolver.

Na programação, muitas vezes você encontrará funções recursivas usadas em estruturas de dados e algoritmos como árvores, gráficos e pesquisas binárias.

Exemplos de função recursiva do Python

Vamos dar alguns exemplos de uso de funções recursivas do Python.

1) Um exemplo simples de função recursiva em Python

Suponha que você precise desenvolver uma função de contagem regressiva que faça a contagem regressiva de um número especificado até zero.

Por exemplo, se você chamar a função que faz a contagem regressiva de 3, ela mostrará a seguinte saída:

3
2
1

O seguinte define a função count_down():

def count_down(start):
    """ Count down from a number  """
    print(start)

Se você chamar a função count_down() agora:

count_down(3)

…ele mostrará apenas o número 3.

Para mostrar os números 3, 2 e 1, você precisa:

• Primeiro, chamar a função count_down(3) para mostrar o número 3.
• Em segundo lugar, chamar a função count_down(2) para mostrar o número 2.
• Finalmente, chamar a função count_down(1) para mostrar o número 1.

Para isso, dentro da função count_down(), você precisará definir uma lógica para chamar a função count_down() com o argumento 2 e 1.

Para fazer isso, você precisa tornar a função count_down() recursiva.

O seguinte define uma função count_down() recursiva e a chama passando o número 3:

def count_down(start):
    """ Count down from a number  """
    print(start)
    count_down(start-1)


count_down(3)

Se você executar o programa, verá o seguinte erro:

RecursionError: maximum recursion depth exceeded while calling a Python object

O motivo é que a função count_down() chama a si mesmo indefinidamente até que o sistema o interrompa.

Como você precisa parar a contagem regressiva, o número chega a zero. Para fazer isso, você adiciona uma condição como esta:

def count_down(start):
    """ Count down from a number  """
    print(start)

    # call the count_down if the next
    # number is greater than 0
    next = start - 1
    if next > 0:
        count_down(next)


count_down(3)

Saída:

3
2
1

Neste exemplo, a função count_down() só chama a si mesma quando o próximo número for maior que zero. Em outras palavras, se o próximo número for zero, ele para de chamar a si mesmo.

2) Usando uma função recursiva para calcular a soma de uma sequência

Suponha que você precise calcular a soma de uma sequência, por exemplo, de 1 a 100. Uma maneira simples de fazer isso é usar um loop for com a função range():

def sum(n):
    total = 0
    for index in range(n+1):
        total += index

    return total


result = sum(100)
print(result)

Saída:

5050

Para aplicar a técnica de recursão, você pode calcular a soma da sequência de 1 a n da seguinte forma:

• soma(n) = n + soma(n-1)
• soma(n-1) = n-1 + soma(n-2)
• …
• soma(0) = 0

A função sum() continua chamando a si mesma enquanto seu argumento for maior que zero.

O seguinte define a versão recursiva da função sum():

def sum(n):
    if n > 0:
        return n + sum(n-1)
    return 0


result = sum(100)
print(result)

Como você pode ver, a função recursiva é muito mais curta e legível.

Se você usar o operador ternário, a função sum() será ainda mais conciso:

def sum(n):
    return n + sum(n-1) if n > 0 else 0


result = sum(100)
print(result)

Resumo

• Uma função recursiva é uma função que chama a si mesma até que não o faça.
• E uma função recursiva sempre tem uma condição que para de chamar a si mesma.