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! = 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:
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)
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.
