Introdução básica à Recursividade
Uma rotina é recursiva quando ela chama a si mesma repetidamente para a resolução de um problema. Apesar de se ter uma definição simples, a recursividade nem sempre é algo fácil de entender.
Ela é uma estratégia utilizada na ciência da computação que consiste em dividir um problema grande em problemas menores e cada vez mais fáceis de se resolver, até chegar em um que seja simples o suficiente para ser resolvido sem dificuldade.
Quando chegamos nesta última resolução do problema, este informa sua resolução para o problema anterior, que por sua vez, comunica ao anterior e assim, sucessivamente, até se chegar na resolução do problema inicial.
Para a execução de uma função recursiva, é necessário que ela siga três regras básicas, que são:
- Uma função recursiva deve ter um caso base, ou seja, que encerra sua execução quando a função chega nele.
- Uma função recursiva deve mudar seu estado e se aproximar do caso base a cada nova chamada de sua função, e aproximar daquele resultado que é previsto como o resultado final.
- E, por último, um algoritmo recursivo obviamente deve chamar a si mesmo recursivamente.
Como exemplo podemos citar o jogo das bonecas Matrioska. O objetivo consiste em pegar a última boneca, a menor de todas, abrindo boneca por boneca. Este é o nosso caso base.
Vamos então chamar a nossa função retirarMatrioska(). Esta função primeiramente vai verificar se a última boneca foi retirada. Se ela tivesse sido retirada nossa função se encerraria, mas não é este o caso em nosso exemplo. Logo após a verificação, a função retira uma das bonecas e em seguida chama a função retirarMatrioska() novamente.
Desta forma, a nossa função retirarMatrioska() só vai parar de ser executada quando a última boneca, a menor de todas, for retirada.
Nossa função retirarMatrioska() possui as três regras básicas da recursão. Primeiro, ela tem um fim previsto quando a última Matrioska é retirada. A cada nova chamada da função, nos aproximamos do seu resultado final. Por fim, ela chama a si mesma, ou seja, uma função recursiva.
https://www.lucasmantuan.com.br https://github.com/lucasmantuan https://www.linkedin.com/in/lucasmantuan
Complementando (sei que a intenção foi dar uma ideia básica, mas acho que vale a pena aprofundar só um pouquinho, com alguns pontos que eu acho importante)...
Recursão (ou recursividade) é uma daquelas coisas que no começo é difícil de entender, mas depois que entende, muita gente se empolga e quer usar em "tudo".
Mas você não deveria usar pra tudo. Na verdade, no dia-a-dia você vai usar menos do que imagina. A maioria dos problemas mais comuns encontrados em grande parte dos sistemas podem ser resolvidos com um loop simples em vez de recursão.
Claro que é importante saber o conceito (pois um dia vai ter um caso que é melhor resolvido com recursão), mas é mais importante ainda saber quando não usar (pois tais casos não são a regra).
Exemplo
Um exemplo clássico é o cálculo do fatorial. Esse é muito usado para ensinar recursão, justamente porque a definição matemática é recursiva. Para calcular o fatorial de um número N, basta fazer:
- se N é zero, o resultado é 1
- senão, o resultado é N * fatorial(N - 1)
E aí segue a implementação clássica (todos os exemplos abaixo estão em JavaScript):
function recursiveFat(n) {
if (n == 0) {
return 1;
}
return n * recursiveFat(n - 1);
}
Atenção: nenhuma das funções mostradas vai verificar se
né um número negativo, por preguiça para simplificar os exemplos :-)
E isso funciona, mas tem alguns detalhes (que muita gente esquece de explicar quando ensina recursão).
Ao se chamar uma função, a chamada é empilhada no stack (ou "colocada na pilha"), e fica lá até que a função retorne. Mas como o resultado de uma chamada depende de outra chamada recursiva, as funções só serão desempilhadas quando a última destas chamadas retornar.
Por exemplo, se eu chamo recursiveFat(2):
- a chamada
recursiveFat(2)é empilhada - não cai no
if(poisné igual a 2), e chaman * recursiveFat(n - 1), ou seja,2 * recursiveFat(1). Para ter este resultado, eu preciso saber qual o valor derecursiveFat(1), então precisamos executá-la primeiro- a chamada
recursiveFat(1)é empilhada - não cai no
if(poisné igual a 1), e chaman * recursiveFat(n - 1), ou seja,1 * recursiveFat(0). Para ter este resultado, eu preciso saber qual o valor derecursiveFat(0), então precisamos executá-la primeiro- a chamada
recursiveFat(0)é empilhada - agora cai no
if, poisné igual a zero, então retorna1
- a chamada
recursiveFat(0)retornou1, então agora conseguimos calcular1 * recursiveFat(0)->1 * 1->1
- a chamada
recursiveFat(1)retornou1, então agora conseguimos calcular2 * recursiveFat(1)->2 * 1->2
O resultado é 2. Mas veja que, para recursiveFat(2) retornar, ela teve que ficar esperando recursiveFat(1) terminar, que por sua vez teve que esperar recursiveFat(0) terminar. Durante todo esse tempo, todas as 3 chamadas estavam ocupando espaço na pilha.
O problema é que a pilha tem tamanho limitado. Por exemplo, se chamarmos recursiveFat(100000), vai dar erro:
RangeError: Maximum call stack size exceeded
São tantas chamadas recursivas "penduradas", esperando as demais terminarem, que estourou o tamanho da pilha.
Se eu fizesse o algoritmo iterativo (com um loop simples), isso não aconteceria:
function iterativeFat(n) {
var fat = 1;
// não preciso multiplicar por 1 porque não muda nada, posso começar do 2 mesmo
// se n for menor que 2, ele nem entra no for e o resultado será 1
for (var i = 2; i <= n; i++) {
fat *= i;
}
return fat;
}
Obs: agora se eu chamar iterativeFat(100000) vai dar Infinity, mas isso é porque o resultado ultrapassa o valor máximo que o Number do JavaScript suporta. Se quiser mesmo ter o resultado, pode trocar para BigInt, bastando colocar o sufixo n nos números: var fat = 1n e for (var i = 2n; etc. Independente disso, o importante é que agora só temos uma única chamada da função (contra várias chamadas da versão recursiva), portanto não vai estourar a pilha (pode estourar a memória se os números começarem a ficar grandes demais, claro, mas aí não tem jeito, fatorial cresce muito rápido).
E além de não estourar a pilha, a versão iterativa ainda é mais rápida, veja.
Não estou dizendo que recursão é "do mal" ou que nunca deva ser usada. É um conceito importante e tem seus usos. Por exemplo, em árvores, que são estruturas naturalmente recursivas: alguns algoritmos para percorrer o DOM de uma página (que é uma árvore) podem ser melhores expressos de forma recursiva. Mas a maioria dos casos mais comuns do dia-a-dia pode ser resolvida com um loop simples.
Além disso, de maneira geral, todo algoritmo iterativo pode ser convertido para um recursivo e vice-versa. Mas só porque pode, não quer dizer que você deve fazê-lo. Muitas vezes um deles será bem melhor (mais simples, mais claro e/ou mais eficiente) que o outro.
O importante é entender o conceito, seus prós e contras, quais problemas ele resolve bem e em quais casos ele não é o mais adequado, e aí decidir quando usar ou não (aliás, isso vale pra tudo em computação).