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

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.

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.

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.

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.

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!

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'!

Por fim, para realmente entender recursão, leia este artigo de novo!