Recursividade: o que é?

Entenda o significado do conceito matemático da recursividade e veja alguns exemplos de problemas reais onde ela é aplicada.

09/11/2023

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:

recursividade

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:

recursividade

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

Crave a enxada no solo

Passo 1

Retire um montante de terra

Passo 2

Coloque a terra retirada em uma outra região

Passo 3

O buraco atingiu 1m de profundidade?
Caso sim: termine a tarefa
Caso contrário: volte para o passo 1

Passo 4

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

Molhe o pano na água

Passo 1

Torça o pano

Passo 2

Passe o pano sobre uma pequena região suja

Passo 3

Ainda existem regiões sujas?
Caso existam: volte para o passo 1
Caso contrário: termine a tarefa

Passo 4

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.

recursividade

Passo 1

recursividade

Passo 2

recursividade

Passo 3

recursividade

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:

recursividade

Triângulo inteiro

recursividade

Subdividimos o triângulo

recursividade

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.

recursividade

Três pedaços resultantes da etapa anterior

recursividade

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

recursividade

Pedaços resultantes

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

recursividade

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:

5! = 5×4×3×2×1 = 120
4! = 4×3×2×1 = 24
3! = 3×2×1 = 6

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:

n! = n × (n-1)! : Fatorial de n é igual a n multiplicado pelo Fatorial de n menos 1.

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.

4! = 4 × (3)! : Fatorial de 4 é igual a 4 multiplicado pelo Fatorial de 3.
3! = 3 × (2)! : Fatorial de 3 é igual a 3 multiplicado pelo Fatorial de 2.
2! = 2 × (1)! : Fatorial de 2 é igual a 2 multiplicado pelo Fatorial de 1.
1! = 1: Fatorial de 1 é sempre igual a 1

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:

recursividade

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).

recursividade

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

recursividade

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

recursividade

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

recursividade

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

recursividade

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

fib(n) = fib(n-1) + fib(n-2)
Ou seja: o n-ésimo termo é igual ao penúltimo mais o antepenúltimo.

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

fib(5º) = fib(4º) + fib(3º)
fib(4º) = fib(3º) + fib(2º)
fib(3º) = fib(2º) + fib(1º)
fib(2º) = 1
fib(1º) = 1

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.

autor

David Santiago

Mestre em Sistemas e Computação. Graduado em Sistemas de Informação. Professor de Linguagem de Programação, Algoritmos, Estruturas de Dados e Desenvolvimento de Jogos Digitais.

Outros artigos