Recursividade: o que é?

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

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

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.

Exemplo 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:

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! = 1Fatorial 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:

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:

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

Compartilhe este artigo

Share on whatsapp
WhatsApp
Share on facebook
Facebook
Share on twitter
Twitter
Share on linkedin
LinkedIn
Share on email
Email

Nos siga
em nossas redes sociais.