Alguém aí já usou recursão?

Esse post foi escrito em resposta ao seguinte tweet:

https://twitter.com/cakebelz/status/1612620889262006274

Antes de mais nada, que fique claro: recursão pode ser vista como uma alternativa a loops. Tudo que você pode fazer com um, você pode fazer com outro. Sem loops e recursão, porém, certas coisas seriam impossíveis de fazer. De certa forma, loops e recursão são o "combustível" da computação, eles capturam o conceito de "repetição", permitindo você fazer algo várias vezes. Mas se loops são o bastante, então pra que recursão?

Acontece que existem problemas que são muito mais fáceis de expressar, entender, debugar etc. se você utiliza recursão, ao invés de loops. Alguém falou sobre fatorial, mas esse é um exemplo ruim, pois o fatorial em loop é bem simples. Vou tentar dar um exemplo bem simples e claro:

Considere que você tem um JSON representando uma árvore familiar:

{
  nome: "João",
  filho: {
    nome: "Marcelo",
    filho: {nome: "Marcio"},
    filha: {nome: "Marcos"},
  },
  filha: {
    nome: "Maria",
    filho: {nome: "Martinho"},
    filha: {
      nome: "Mariana",
      filho: {nome: "Mariosvaldo"},
      filha: {nome: "Goiaba"},
    },
  }
}

Agora, faça o seguinte: escreva uma função que conta a quantidade de pessoas em uma árvore familiar. Ou seja, que conta todos os descendentes de uma pessoa. Tente fazer isso usando loops. Não, sério: vá e tente. Como ficou? Minha melhor solução é a seguinte:

function contar(pessoa) {
  var soma = 0;
  var fila = [pessoa];
  while (fila.length > 0) {
    var pessoa = fila.pop();
    if (pessoa) {
      soma += 1;
      fila.push(pessoa.filho);
      fila.push(pessoa.filha);
    }
  }
  return soma;
}

Como você pode ver, a solução é meio complicadinha, e propensa a erros, pois a gente precisa manter e administrar manualmente um estado mutável (a soma) e uma fila de pessoas a serem contadas. Além disso, entender esse algoritmo requer fazer um passo-a-passo mental do que acontece com a fila, para garantir que não ficará vazia na hora errada, que não esqueceremos de ninguém, que o loop vai parar no momento certo, e por aí vai. Compare, agora, com a versão recursiva:

function contar(pessoa) {
  if (pessoa) {
    return 1 + contar(pessoa.filho) + contar(pessoa.filha);
  } else {
    return 0;
  }
}

Como você pode ver, o código é muito menor e mais direto. Além disso, não é difícil de entender o que ele faz. As regras é simples: para contar a quantidade de filhos de uma pessoa, basta somar a contagem de filhos dos seus filhos. Vai me dizer que não faz sentido?

Por mais que pareça pouca diferença, essa diferença só aumenta quando se trata de um algoritmo mais complicado. Imagina quando estamos falando não de uma árvore familiar simples, mas de uma rede social com milhares de campos? Manter muitas filas e estados locais é a receita para bugs difíceis de achar, enquanto uma recursão pode ser muito mais fácil de lidar.

Um exemplo mais extremo disso é o problema de encontrar permutações. Isso é, dada uma lista (por exemplo, [1, 2, 3]), encontre todas as permutações. Nesse caso, a resposta seria:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Esse problema pode ser resolvido usando loops, da seguinte forma:

function permutations(inputArr) {
  var results = [];

  function permute(arr, memo) {
    var cur, memo = memo || [];

    for (var i = 0; i < arr.length; i++) {
      cur = arr.splice(i, 1);
      if (arr.length === 0) {
        results.push(memo.concat(cur));
      }
      permute(arr.slice(), memo.concat(cur));
      arr.splice(i, 0, cur[0]);
    }

    return results;
  }

  return permute(inputArr);
}

console.log(permutations([1, 2, 3]));

Agora, me diga: você consegue entender ou explicar essa solução? Talvez a estudando um pouquinho, até consiga, mas, convenhamos, não é o tipo de código que se bate o olho e fica óbvio. A superfície de "bugs bobos" é muito grande, principalmente considerando problemas como acessar um índice errado e similares. Agora, compare com a versão recursiva em Haskell, uma linguagem funcional que tem "monads", uma feature que torna a recursão ainda mais expressiva:

permutations :: Eq a => [a] -> [[a]]
permutations [] = [[]]
permutations list = do
  head <- list
  tail <- permutations (filter (/= head) list)
  return $ head : tail

main = print $ (permutations [1, 2, 3, 4])

Muito menor, não é mesmo? E ele é bem mais fácil de ler e entender. Se olhar direitinho, podemos ver que a implementação recursiva é quase uma tradução direta da explicação em português: "a permutação de uma lista pode ser obtida selecionando o primeiro elemento da lista, e concatenando este elemento à permutação do resto da lista sem o mesmo".

Explicar o que são monads e por que eles permitem que a gente escreva algoritmos de forma tão concisa foge ao escopo desse post, mas espero que tenha ajudado a iluminar o porquê de recursão as vezes ser a ferramenta correta para resolver um determinado problema. Em resumo, recursão e loops são equivalentes em poder, porém são diferentes em sua forma, e fazer a escolha certa pode tornar o seu código mais legível e menos propenso a bugs. Como regra geral, loops são apropriados quando "a repetição" do algoritmo pode ser descrita de forma sequencial ("um após o outro"), enquanto recursão é mais apropriado quando essa repetição "se desdobra" de uma forma mais complicada, como por exemplo ao lidarmos com árvores, grafos, combinatórios, dentre outros.