Funções recursivas 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 fn()função a seguir é uma função recursiva porque possui uma chamada para si mesma:

def fn():
    # ...
    fn()
    # ...
Linguagem de código:  Python  ( python )

Na fn()funçã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()
    # ...
Linguagem de código:  Python  ( python )

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

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

Exemplos de funções recursivas Python

Vejamos 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 a partir de 3, ela mostrará a seguinte saída:

3
2
1Linguagem de código:  Python  ( python )

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

def count_down(start):
    """ Count down from a number  """
    print(start)Linguagem de código:  Python  ( python )

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

count_down(3)Linguagem de código:  Python  ( python )

…mostrará apenas o número 3.

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

• Primeiro, ligue para count_down(3)para mostrar o número 3.
• Em segundo lugar, ligue para count_down(2)para mostrar o número 2.
• Por fim, chame o count_down(1)para mostrar o número 1.

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

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

O seguinte define uma count_down()função 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)Linguagem de código:  Python  ( python )

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

RecursionError: maximum recursion depth exceeded while calling a Python objectLinguagem de código:  Python  ( python )

A razão é que o count_down()auto chama-se 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)Linguagem de código:  Python  ( python )

Saída:

3
2
1Linguagem de código:  Python  ( python )

Neste exemplo, a count_down()função 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 se chamar.

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)Linguagem de código:  Python  ( python )

Saída:

5050Linguagem de código:  Python  ( python )

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 sum()função continua chamando a si mesma enquanto seu argumento for maior que zero.

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

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


result = sum(100)
print(result)Linguagem de código:  Python  ( python )

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

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

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


result = sum(100)
print(result)
Linguagem de código:  Python  ( python )

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.