Artigo original: https://www.freecodecamp.org/news/how-recursion-works-explained-with-flowcharts-and-a-video-de61f40cb7f9/
(A ilustração da capa – bem como tudo neste artigo – é de Aditya Barghava)
"Para entender recursão, você primeiro precisa entender recursão."
A recursão, ou recursividade, pode ser um assunto difícil de entender — especialmente para novos programadores. Em sua forma mais simples, uma função recursiva é uma função que invoca a si mesma. Deixe eu tentar explicar com um exemplo.
Imagine que você vai abrir a porta do seu quarto e encontra a porta trancada. Seu filho de três anos aparece e revela que ele trancou a porta e escondeu a chave em uma caixa ("Bem a cara dele", você pensa). Você está atrasado para o trabalho e precisa urgentemente entrar no quarto para pegar sua camisa.
Você abre a caixa apenas para encontrar... mais caixas! Caixas dentro de caixas. Você não sabe qual delas contêm a chave! Você precisa daquela camisa então decide pensar em um bom algoritmo para resolver este dilema.
Existem duas maneiras principais de se criar um algoritmo para este problema: iterativa e recursiva. Aqui estão ambas as maneiras explicadas com um fluxograma:
![1_QrQ5uFKIhK3jQSFYeRBIRg](https://www.freecodecamp.org/portuguese/news/content/images/2024/04/1_QrQ5uFKIhK3jQSFYeRBIRg.png)
Qual delas parece mais fácil?
A primeira maneira utiliza um laço while. Enquanto a pilha não estiver vazia, pegue uma caixa e verifique-a. Aqui está um pseudocódigo inspirado em Javascript que mostra o que está acontecendo (pseudocódigo é escrito como se fosse código, mas se assemelha a língua humana).
function procura_chave(caixa_principal) {
let pilha = caixa_principal.fazer_pilha_para_procurar();
while (pilha nao vazia) {
caixa = pilha.pegar_caixa();
for (item in caixa) {
if (item.eh_uma_caixa()) {
pilha.append(item)
} else if (item.eh_uma_chave()) {
console.log("achei a chave!")
}
}
}}
A segunda maneira utiliza a recursão. Lembre-se, recursão é quando uma função que invoca a si própria. Aqui está a segunda maneira em pseudocódigo.
function procura_chave(caixa) {
for (item in caixa) {
if (item.eh_uma_caixa()) {
procura_chave(item);
} else if (item.eh_uma_chave()) {
console.log("achei a chave!")
}
}
}
Ambas as abordagens resultam na mesma coisa. O principal propósito de se utilizar recursão é que, depois que você entende o conceito, o código fica mais legível. Não existe nenhum benefício de desempenho ao se usar recursão. A solução iterativa, às vezes, pode ser até mais rápida, mas a simplicidade da recursão é preferida.
Além disso, como muitos algoritmos famosos utilizam recursão, é importante entender como funciona. Se recursão ainda não soa simples para você, não se preocupe: darei mais alguns exemplos.
Caso base e caso recursivo
Uma coisa que você deve tomar muito cuidado ao escrever uma função recursiva é com um laço infinito. Isso ocorre quando a função continua se invocando... e nunca para!
Por exemplo, se você quiser escrever uma função de contagem regressiva. Você poderia escrevê-la recursivamente em Javascript desse jeito:
// CUIDADO: esta função contém um laço infinito!
function contagemRegressiva(i) {
console.log(i)
contagemRegressiva(i - 1)
}
contagemRegressiva(5); // Essa é a chamada inicial da função.
![1_LGjfggsIiQHbfJothG1hYw](https://www.freecodecamp.org/portuguese/news/content/images/2024/04/1_LGjfggsIiQHbfJothG1hYw.png)
Essa função continuará se invocando pra sempre. Se você acidentalmente criou um código com um laço infinito, pode apertar "Ctrl+C" para encerrar seu script (ou, se estiver no CodePen, precisará adicionar "?turn_off_js=true" no fim da URL.)
Uma função recursiva sempre precisará de uma condição para dizer quando ela precisa parar de se invocar. Sempre existirão duas partes de uma função recursiva: O caso recursivo e o caso base. O caso recursivo é quando a função invoca a si mesma. O caso base é quando a função deverá parar de se invocar. Isso evitará os laços infinitos.
Aqui está a contagem regressiva novamente, desta vez com um caso base:
function contagemRegressiva(i) {
console.log(i)
if (i <= 1) { // caso base
return;
} else { // caso recursivo
contagemRegressiva(i - 1);
}
}
contagemRegressiva(5); // Essa é a chamada inicial da função.
![1_rQ9Z3DmtGk1Bb6_Mx5W6rQ](https://www.freecodecamp.org/portuguese/news/content/images/2024/04/1_rQ9Z3DmtGk1Bb6_Mx5W6rQ.png)
Pode não ser óbvio o que está acontecendo nessa função. Vou explicar o que acontece quando se executa a função contagemRegressiva
passando "5" como argumento.
Começamos imprimindo o número 5 no console utilizando console.log
. Como cinco não é menor ou igual a um, vamos para o bloco else. Lá, invocamos novamente a função contagemRegressiva
com o número quatro (5-1=4).
Imprimimos o número 4. Novamente, i
não é menor ou igual a um, então vamos para o bloco else e invocamos a função contagemRegressiva
novamente com o argumento 3. Esse processo continua até i
ser igual a um. Quando isso acontecer, imprimimos o número um e então i
será menor ou igual a um. Finalmente chegamos à declaração de retorno, então encerramos o laço e saímos da função.
Call stack
Funções recursivas utilizam algo chamado "call stack" (ou "pilha de chamadas", em português). Quando um programa invoca uma função, essa função vai para o topo dessa pilha. Essa estrutura é similar à uma pilha de livros. Você adiciona livros na pilha um de cada vez. Então quando você quer retirar um livro da pilha, você sempre tira primeiro o livro do topo.
Vou mostrar a pilha de chamadas em ação com a função fatorial
. A expressão fatorial(5)
é escrita como 5! e é definida assim: 5! = 5 * 4 * 3 * 2 * 1. Aqui está uma função recursiva para calcular o fatorial de um número.
function fatorial(x) {
if (x == 1) {
return 1;
} else {
return x * fatorial(x-1);
}
}
Agora, vamos ver o que acontece se você chamar fatorial(3)
. A ilustração abaixo mostra como a pilha de chamada (call stack) funciona, linha por linha. A chamada mais ao topo da pilha mostra qual chamada de fatorial
(no exemplo em inglês, fact
) está sendo executada no momento.
![1_YRkMsMPRFAt8Y9BiC0QVDg](https://www.freecodecamp.org/portuguese/news/content/images/2024/04/1_YRkMsMPRFAt8Y9BiC0QVDg.png)
![1_AWu17xnQ-lxVwpgVhEo_lA](https://www.freecodecamp.org/portuguese/news/content/images/2024/04/1_AWu17xnQ-lxVwpgVhEo_lA.png)
Note como cada chamada de fatorial
tem sua própria cópia de x
. Isso é muito importante para fazer com que a recursão funcione. Você não pode acessar a cópia de x
de uma função diferente.
Já encontrou a chave?
Vamos voltar brevemente ao exemplo original sobre procurar a chave nas caixas aninhadas. Lembre-se, o primeiro método foi iterativo utilizando um laço while. Com aquele método, você primeiro alinha as caixas e depois procura em cada uma delas, assim você sempre sabe em quais caixas você ainda precisa procurar.
![1_qFezr1s9YpK6-GsMJqwhOA](https://www.freecodecamp.org/portuguese/news/content/images/2024/04/1_qFezr1s9YpK6-GsMJqwhOA.png)
Essa abordagem, porém, não existe no método recursivo. Como seu algoritmo sabe em quais caixas você ainda precisa procurar? A "pilha de caixas" é salva na stack. Essa stack consiste em chamadas de funções "meio completas", cada uma com suas listas "meio completas" para serem verificadas. A stack gerencia toda essa pilha para você!
Graças à recursão, você pode finalmente encontrar a chave e pegar sua camisa!
![1_8Y0_goJ5oKvt1tzSX4d8Tw](https://www.freecodecamp.org/portuguese/news/content/images/2024/04/1_8Y0_goJ5oKvt1tzSX4d8Tw.png)
Você também pode assistir esse vídeo (em inglês) de 5 minutos sobre recursão. Isso vai ajudar a reforçar esses conceitos de recursão.
Conclusão
Espero que este artigo tenha trazido mais clareza sobre recursão na programação. Este artigo é baseado em meu novo curso na Manning Publications chamado Algorithms in Motion (Algoritmos em movimento). O curso (bem como este artigo) é baseado no incrível livro Entendendo algoritmos, de Aditya Bhargava. Foi ele quem desenhou todas as ilustrações deste artigo.
Se você aprende melhor lendo livros, adquira o livro! Se você aprende melhor assistindo vídeos, considere adquirir meu curso (em inglês).
Tenha 39% de desconto no meu curso usando o código '39carnes'!
![1_a5UFtQIHwXy7SCQpI9GdVQ](https://www.freecodecamp.org/portuguese/news/content/images/2024/04/1_a5UFtQIHwXy7SCQpI9GdVQ.png)
Por fim, para realmente entender recursão, leia este artigo de novo!