Aprendendo Funções Recursivas em Python: Guia Completo

O que é uma função recursiva?

O processo de uma função chamar a si própria(direta ou indiretamente) é chamado de recursão e a função é denominada uma função recursiva.

Um algoritmo recursivo(um algoritmo que faz o uso de recursão) em muitos problemas apresentam uma solução mais simples do que as demais formas de escrita de algoritmos.

Na prática, uma função recursiva separa o problema em partes, e resolve cada parte chamando uma cópia de si mesma.

Devido a essa característica, é importante definir um parâmetro de parada para evitar o programa entre em um loop infinito de chamadas recursivas.

Recursividade em Python

Em Python, sabemos que uma função pode chamar outras funções.

Porém, muitos iniciantes em programação nem cogitam a hipótese de uma função chamar a si mesma.

Exemplo simples de recursão em Python

Podemos elaborar uma função recursiva que faça uma contagem a partir de um valor inicial i.

Abaixo temos a abordagem inicial dessa função recursiva:

import time


def contador(i):
    print(i)
    time.sleep(1)
    contador(i + 1)


contador(0)
 

Executando essa função teremos a seguinte saída:

0  
1  
2  
3  
4  
5  
6  
7  
8  
...  

Você provavelmente reparou que esse programa nunca irá encerrar sua execução, o que pode ser um problema, para evitar isso vamos um colocar um critério de continuidade da recursividade.

Um critério de continuidade da recursividade é uma condição que deve ser verdadeira para que a função seja chamada mais uma vez.

No nosso exemplo, chamaremos a função apenas se i for menor que 10:

import time


def contador(i):
    print(i)
    time.sleep(1)
    if i < 10:
        contador(i + 1)


contador(0)

Executando essa função teremos a seguinte saída:

0  
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  

Exemplo intermediário de recursão em Python

No exemplo anterior criamos uma função recursiva que não retorna nada.

Muitas vezes, a vantagem da recursividade é justamente poder utilizar o retorno da função recursivamente.

Um dos exemplos mais clássicos de funções recursivas é a função que retorna o fatorial de um número inteiro.

O fatorial de um número é o produto de todos os inteiros de 1 a esse número. Por exemplo, o fatorial de 8 (indicado como 8!, ler se “oito fatorial”)1 * 2 * 3 * 4 * 5 * 6 * 7* 8 = 40320.

def fatorial(x):
    if x == 1:
        return 1
    else:
        return x * fatorial(x - 1)


print(fatorial(8))

Executando essa função teremos a seguinte saída:

40320  

A cada execução da função, x é multiplicado pelo valor retornado pela função com o antecessor de x(x sendo subtraído por 1).

Nesse exemplo, não temos critério de continuidade da recursividade e sim uma condição base, onde uma constante é retornada(no caso 1) e não uma nova execução da função.

Por razões didáticas a condição foi colocada de forma completa, mas essa função pode ser simplificada com uma condicional de uma lina(one-line if):

def fatorial(x):
    return (x * fatorial(x - 1)) if x > 1 else 1


print(fatorial(8))

Executando essa função o resultado será o mesmo do exemplo anterior(40320).

Conclusão

Nesse artigo foi exposto oque é uma função recursiva e como utilizar essa possibilidade em Python, além disso, foi visto também que toda função recursiva deve ter uma condição base(ou um critério de continuidade) que pare a recursão ou então a função chama a si mesma infinitamente.

Vantagens da recursão

• Funções recursivas fazem o código parecer limpo e elegante.
• Uma tarefa complexa pode ser dividida em sub-tarefas mais simples usando recursão.
• Gerar uma sequência é consideravelmente mais fácil com recursão do que usando alguma iteração aninhada(for/while
  dentro de outro for/while).

Desvantagens da Recursão

• Às vezes, a lógica por trás da recursão é difícil de entender.
• As chamadas recursivas são caras computacionalmente, pois ocupam mais memória do que uma iteração.
• Funções recursivas são difíceis de depurar.