Funcões recursivas¶

Tanto na matemática como na computação, a definição recursiva de um função ocorre quando ela é parcialmente definida (depende) de si própria. Para exemplificar considere o cálculo do fatorial de um número.

Numa primeira abordagem, o fatorial de um número pode ser calculado por meio da expressão:

$$ 5! = 5 \times 4 \times 3 \times 2 \times 1 = 120 $$

Generalizando, o fatorial de úm número n é dado pelo produtório:

$$ n! = \prod_{i = 1}^{n} i = 1 \times 2 \times \dots \times (n-1)\times n $$

Em Python esse produtório pode ser implementado com base num processo iterativo como:

In [ ]:
# Cálculo do fatorial de n

n = int(input())
fat = 1
for i in range(2, n+1):
    fat *= i
print(fat)

Uma segunda forma de expressar o cálculo do fatorial de num número é por meio da função recursiva:

$$ n! = \begin{cases} 1 & \quad\text{se n = 0} \quad\text{(a base ou ponto de parada)} \\ n \times (n-1)! & \quad\text{em outros casos} \quad\text{(o passo recursivo)} \end{cases} $$

Observe que a função fatorial (!) é utilizada para definir a si própria, caracterizando a forma mais simples de definição recursiva. A animação abaixo mostra como ocorre o cálculo de 5!:

Fatorial

A cada passo recursivo é criada uma nova instância da função, resultando num empilhamento das instâncias. Isto ocorre porque cada instância precisa aguardar o resultado do cálculo da instância posterior antes de poder completar o seu cálculo. Este empilhamento se repete até que seja alcançado um ponto base (de parada). A partir dai o resultado é retornado para o nível anterior, causando um desempilhamento progressivo das instâncias na medida que elas vão completando seus correspondentes cálculos.

Note que num instante qualquer de tempo há apenas uma das instâncias da função em execução, estando todas as demais paradas, como que adormecidas. É como se houvesse um bastão (analogia com uma corrida de 4x100m do atletismo) que vai sendo passado de uma instância da função para outra. Apenas a instância que tem o bastão está em execução, ficando todas as demais paradas aguardando que lhe seja passado o bastão.

Uma implementação para essa função recursiva em Python é:

In [ ]:
# Função recursiva para cálculo do fatorial de n
def fatorial(n):
    if n == 0:
        return 1 # a base ou ponto de parada
    else:
        return n * fatorial(n-1) # o passo recursivo
    
n = int(input())
print(fatorial(n))

Outro exemplo de função recursiva é esta abaixo que calcula o máximo divisor comum (MDC) de dois números utilizando o algoritmo de Euclides:

$$ mdc(a, b) = \begin{cases} a & \quad\text{se b = 0} \quad\text{(a base ou ponto de parada)} \\ mdc(b, a \% b) & \quad\text{em outros casos} \quad\text{(o passo recursivo)} \end{cases} $$

(*) o operador % corresponde ao resto da divisão inteira

Esta função pode ser implementada em Python conforme abaixo:

In [ ]:
def mdc(a, b):
    if b == 0:
        return a
    else:
        return mdc(b, a%b)
    
n1 = int(input())
n2 = int(input())
print(mdc(n1, n2))

A animação que segue mostra como ocorre o cálculo do MDC de 1320 e 35:

MED