Executando verificação de segurança...
4

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 (pois n é igual a 2), e chama n * recursiveFat(n - 1), ou seja, 2 * recursiveFat(1). Para ter este resultado, eu preciso saber qual o valor de recursiveFat(1), então precisamos executá-la primeiro
    • a chamada recursiveFat(1) é empilhada
    • não cai no if (pois n é igual a 1), e chama n * recursiveFat(n - 1), ou seja, 1 * recursiveFat(0). Para ter este resultado, eu preciso saber qual o valor de recursiveFat(0), então precisamos executá-la primeiro
      • a chamada recursiveFat(0) é empilhada
      • agora cai no if, pois n é igual a zero, então retorna 1
    • recursiveFat(0) retornou 1, então agora conseguimos calcular 1 * recursiveFat(0) -> 1 * 1 -> 1
  • recursiveFat(1) retornou 1, então agora conseguimos calcular 2 * 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).

Carregando publicação patrocinada...
2

Opa, só para entender melhor. Para contornar este problema do estouro de pilha eu poderia otimizar a função recursiva, algo como:

function tailRecursiveFat(n, resultado = 1) {
    if (n == 0) {
        return resultado;
    }
    return tailRecursiveFat(n - 1, n * resultado);
}

Mas, coloquei ela no site de testes, e para este exemplo que você passou o loop for ainda é mais rápido.

3

Isso só elimina o estouro de pilha em linguagens que otimizam a recursão em cauda - o que não é o caso do JavaScript, pois ainda sim estoura a pilha, veja: https://ideone.com/n6mFHd

Ah, vale lembrar que o número que faz a pilha estourar pode variar, pois depende de detalhes da implementação. Mas o JavaScript (pelo menos na versão atual) não otimiza recursão em cauda, então para evitar o estouro em todos os casos, só usando loop mesmo.


Obs: parece que o Safari otimiza recursão em cauda, mas os demais pelo jeito não (testei no Node, e também estourou a pilha).