Algoritmos #07 - Algoritmos recursivos

Por Bruno Henrique - agosto 10, 2019

A recursão é um dos mecanismos mais úteis da programação, pois, é capaz de reduzir de forma satisfatória o custo e o tempo gasto por algoritmos considerados complexos. Uma função pode ser considerada recursiva quando ela chama a si própria de dentro de seu escopo, seja direta, quando uma certa função X inicia a execução da própria função X, ou indiretamente, quando uma função X chama uma função Y, que, por sua vez, chama novamente a função X.

O principal diferencial da recursão é a divisão de um problema em vários sub-problemas, similares ao original, cuja resolução é mais simples, o que torna o código mais rápido e limpo. Por isso, este post foi criado para apresentar alguns algoritmos recursivos bastante conhecidos e as características através das quais eles facilitam a vida do programador.

Tomemos o cálculo do fatorial como exemplo:

Na matemática, o fatorial de um número n (n!) é definido como o produto de todos os números naturais entre 1 e n (1 x 2 x ... x n - 2 x n - 1 x n). Por exemplo, o fatorial de 5 é dado por 5! = 1 x 2 x 3 x 4 x 5 = 120.

Como (n - 1)! = 1 x 2 x ... x n - 2 x n - 1, podemos dizer que n! = n x (n - 1)!, este será o passo recursivo da nossa função. Como 1 é o primeiro número no cálculo do fatorial, o fatorial de 1 é igual ao próprio 1, por isso, ele será o nosso caso base (condição de parada).

Com isso em mente, podemos implementar o código da seguinte forma:

Utilizando o nosso algoritmo para calcular 5!, temos:

1ª execução: fatorial de 5 = 5 * fatorial de 4
2ª execução: fatorial de 5 = 5 * 4 * fatorial de 3
3ª execução: fatorial de 5 = 5 * 4 * 3 * fatorial de 2
4ª execução: fatorial de 5 = 5 * 4 * 3 * 2 * fatorial de 1
Resultado final: fatorial de 5 = 5 * 4 * 3 * 2 * 1 = 120

Outros exemplos:

Sequência de Fibonacci:

A Sequência de Fibonacci (1, 1, 2, 3, 5, 8, ...), a sucessão de números mais famosa da matemática, tem como característica principal o fato de que cada elemento é definido pelo resultado da soma dos dois elementos anteriores. Dessa forma, também é possível determinar os seus valores de forma recursiva.

Suponha que você quer descobrir qual o número que está na posição n da Sequência de Fibonacci. Assim:

Casos base: o elemento das posições 0 e 1 é o 1.
Passo recursivo: o número na posição n é igual a soma dos valores das posições (n - 1) e (n - 2).

Exemplo de implementação:

Utilizando o algoritmo para calcular o elemento na 4ª posição, temos:

fib de 4 = fib de 3 + fib de 2

fib de 3 = fib de 2 + fib de 1

fib de 2 = fib de 1 + fib de 0

fib de 1 = 1
fib de 0 = 1

fib de 2 = 1 + 1 = 2
fib de 1 = 1

fib de 3 = 2 + 1 = 3

fib de 2 = fib de 1 + fib de 0

fib de 1 = 1
fib de 0 = 1

fib de 2 = 1 + 1 = 2

Resultado final: fib de 4 = 3 + 2 = 5

QuickSort:

O QuickSort, já apresentado no blog anteriormente, é um exemplo bastante conhecido de uso da recursão. Nele estão bem visíveis os benefícios trazidos por tais tipos de algoritmo em relação à eficiência. No código a seguir, a função quicksort chama a si própria duas vezes, uma contendo os algarismos maiores que o pivô e outra contendo aqueles que são menores que o mesmo.

Para saber mais: Algoritmos eficientes de ordenação

Exemplo de implementação: