Recursividade: o que é?

Definição de recursividade

A recursividade é um conceito matemático que define um processo de repetições sucessivas de um determinado fenômeno. Da maneira mais simplificada possível, a recursividade pode ser compreendida como a execução de um procedimento de maneira repetitiva. Quando a solução de um problema consiste em várias repetições de um mesmo procedimento.

Veja um exemplo clássico de recursividade, o efeito droste:

O efeito droste define uma imagem que é formada por repetições sucessivas dela própria.

Um outro exemplo, observável no mundo real, é a recursividade de reflexos entre espelhos paralelos:

Quando dois espelhos são colocados em paralelo é formada uma série de repetições dos seus reflexos de maneira recursiva.

Para começar a entender o significado da recursividade, vamos observar alguns exemplos de atividades sendo resolvidas de maneira recursiva.

A atividade de cavar um buraco de 1m de profundidade

Perceba que a atividade de cavar um buraco consiste na repetição sucessiva de um mesmo conjunto de passos, até que a condição “atingir 1m de profundidade” seja alcançada!

A atividade de limpar o chão de uma sala

Perceba que a atividade de limpar o chão de uma sala também consiste na repetição sucessiva de um mesmo conjunto de passos, até que a condição “não existir regiões sujas” seja alcançada!

Observe que essas atividades são executadas como uma sequência de etapas que terminam reiniciando o ciclo. Ou seja, ao final da atividade, repete-se tudo novamente.

Exemplos de problemas com recursividade

Vamos ver na prática as situações reais nas quais o conceito da recursividade se aplica:

A recursividade na construção do triângulo de Sierpinski

O triângulo de Sierpinski é uma figura geométrica fractal. Sua construção é dada por um processo recursivo de divisão de triângulos em triângulos menores. Observe abaixo uma ilustração que mostra o que é o triângulo de Sierpinski.

Passo 1

Passo 2

Passo 3

Passo 4

Observe como ele é construído pela repetição de um mesmo procedimento: a divisão de um triângulo em outros três pedaços:

Triângulo inteiro

Subdividimos o triângulo

Pedaços resultantes

Uma vez que o triângulo foi dividido, o processo de construção continua para cada um dos 3 novos pedaços resultantes da etapa anterior.

Três pedaços resultantes da etapa anterior

Cada um subdivide-se novamente em outros 3 pedaços

Pedaços resultantes

Observe abaixo uma animação desse processo de subdivisão.

Perceba como a construção do triângulo de Sierpinski é um problema onde a recursividade está presente. A sua construção se resume à repetição de um mesmo procedimento de subdivisão de triângulos.

A recursividade no Número Fatorial

Outro problema que possui natureza recursiva é o Fatorial, que é representado pela simbologia “n!”. Dessa forma, o fatorial de 5 é simbolizado como “5!”.

O cálculo do Fatorial se dá por meio do produto dos números inteiros consecutivos entre 1 e n. Veja os exemplos:

A natureza recursiva do número Fatorial está no fato de que ele é dado pela multiplicação do valor n por seu antecessor de maneira consecutiva. Ele poderia ser representado da seguinte maneira:

Desta forma, o cálculo do fatorial de um número compreende numa série de etapas de cálculo do fatorial de um número cada vez menor.

Perceba no exemplo acima que o cálculo é uma sequência repetida de um mesmo procedimento.

A recursividade na Sequência de Fibonacci

A sequência de Fibonacci é uma sucessão de números da seguinte forma:

Pode parecer apenas uma sequência aleatória de números, mas a sequência possui uma regra bem interessante que define a sua formação: com exceção dos dois primeiros valores, os valores são formados pela soma dos seus dois antecessores.

Observe na sequência como o valor 2 é formado pela soma dos dois antecessores (1 e 1).

De forma semelhante, o valor 3​ é formado pela soma de 2 mais 1.

O valor 5 é formado pela soma de 3 mais 2.

O valor 8 é formado pela soma de 5​ mais 3.

O valor 13 é formado pela soma de 8 mais 5.

A natureza recursiva da sequência de Fibonacci está no fato de que o n-ésimo termo da sequência é encontrado da seguinte maneira:

Desta forma, o cálculo do 5º termo da sequência de Fibonacci é realizado da seguinte maneira:

Perceba no exemplo acima que o cálculo do n-ésimo termo de Fibonacci é uma sequência repetida de um mesmo procedimento de soma de seus dois antecessores.

Uma área onde a recursividade é bastante utilizada é a Ciência da Computação. Nela, o conceito é utilizado para a implementação dos Algoritmos Recursivos. Clique neste link e acesse o artigo onde te explicamos detalhadamente sobre os Algoritmos Recursivos.